Bauxite residue is the alkaline byproduct generated when alumina is extracted from bauxite ores and is commonly deposited in impoundments. These sites represent hostile environments with increased salinity and alkalinity and little prospect of revegetation when left untreated. This study reports the establishment of bacterial communities in bauxite residues with and without restoration amendments (compost and gypsum addition, revegetation) in samples taken in 2009 and 2011 from 0 to 10 cm depth. DNA fingerprint analysis of bacterial communities based on 16S rRNA gene fragments revealed a significant separation of the untreated site and the amended sites in both sampling years. 16S amplicon analysis (454 FLX pyrosequencing) revealed significantly lower alpha diversities in the unamended in comparison to the amended sites and hierarchical clustering separated the unamended site from the amended sites. The taxonomic analysis revealed that the restoration resulted in the accumulation of bacterial populations typical for soils including Acidobacteriaceae, Nitrosomonadaceae, and Caulobacteraceae. In contrast, the unamended site was dominated by taxonomic groups including Beijerinckiaceae, Xanthomonadaceae, Acetobacteraceae, and Chitinophagaceae, repeatedly associated with alkaline salt lakes and sediments. While bacterial communities developed in the initially sterile bauxite residue, only the restoration treatments created diverse soil-like bacterial communities alongside diverse vegetation on the surface.