Land degradation deteriorates biological productivity and affects environmental, social, and economic sustainability, particularly so in the semi-arid region of Northeast Brazil. Although some studies exist reporting gross measures of soil microbial parameters and processes, limited information is available on how land degradation and restoration strategies influence the diversity and composition of soil microbial communities. In this study we compare the structure and diversity of bacterial communities in degraded and restored lands in Northeast Brazil and determine the soil biological and chemical properties influencing bacterial communities. We found that land degradation decreased the diversity of soil bacteria as indicated by both reduced operational taxonomic unit (OTU) richness and Shannon index. Soils under native vegetation and restoration had significantly higher bacterial richness and diversity than degraded soils. Redundancy analysis revealed that low soil bacterial diversity correlated with a high respiratory quotient, indicating stressed microbial communities. By contrast, soil bacterial communities in restored land positively correlated with high soil P levels. Importantly, however, we found significant differences in the soil bacterial community composition under native vegetation and in restored land, which may indicate differences in their functioning despite equal levels of bacterial diversity.