The ecological staircase of Mendocino (California, USA) is characterized by a succession of uplifted marine terraces that are derived from the same mineralogical parent material but have different ages, levels of fertility, and types of vegetation, from grassland in the youngest and most fertile terrace to a pygmy forest in the older terraces. Such conditions present a unique opportunity to determine how the structure, abundance, and function of bacterial communities vary with soil fertility along this natural chronosequence. Pyrosequencing analysis of 16S rRNA gene amplicons revealed that Acidobacteria, Proteobacteria, Actinobacteria, and Bacteroidetes were the most abundantly represented phyla. Bacteroidetes, Firmicutes, Verrucomicrobia were significantly enriched in the grasslands, while the less fertile forested terraces showed higher abundance of Acidobacteria Gp2 and Alphaproteobacteria. The pygmy forest soil harboured significantly more Actinobacteria and OP10 than the non-pygmy forest. Between samples from different terraces, the structure of the bacterial community clearly correlated with soil characteristics. Notably, the number of operational taxonomic units was greater in the fertile terrace, as was the density of culturable bacterial populations. Functional characterization of the soil culturable bacteria from the pygmy and non-pygmy forest terraces revealed that the soil bacteria from the non-pygmy terrace were significantly more effective in solubilizing minerals and more abundant than in the pygmy terrace. Our results provide new information on bacterial community structure as a function of soil age, land cover and fertility, which improve our understanding of soil evolution.