Mining activity for rare earth elements (REEs) has caused serious environmental pollution, particularly for soil ecosystems. However, the effects of REEs on soil microbiota are still poorly understood. In this study, soils were collected from abandoned sites of a REEs mine, and the structure, diversity, and co-occurrence patterns of soil microbiota were evaluated by Illumina high-throughput sequencing targeting 16S rRNA genes. Although microbiota developed significantly along with the natural restoration, the microbial structure on the site abandoned for 10 years still significantly differed from that on the unmined site. Potential plant growth promoting bacteria (PGPB) were identified by comparing 16S sequences against a self-constructed PGPB database via BLAST, and it was found that siderophore-producing and phosphorus-solubilizing bacteria were more abundant in the studied soils than in reference soils. Canonical correspondence analysis indicated that species richness of plant community was the prime factor affecting microbial structure, followed by limiting nutrients (total carbon and total nitrogen) and REEs content. Further co-occurring network analysis revealed nonrandom assembly patterns of microbiota in the studied soils. These results increase our understanding of microbial variation and assembly pattern during natural restoration in REE contaminated soils.