Biological soil crusts (BSCs) have important ecological functions in arid and semiarid lands, but they remain poorly understood in terms of the changes in microbial communities during BSC succession under in situ field conditions. Here, 454 pyrosequencing was used to assess the microbial community composition of four BSC types in the Tengger Desert of China: alga, lichen (cyanolichen and green alga-lichen), and moss crusts, representing early, middle, and final successional stages of BSCs, respectively. The results showed the highest diversity of microbial communities inhabiting lichen crusts, whereas the lowest diversity was observed in moss crusts. Five phyla, Proteobacteria, Actinobacteria, Cyanobacteria, Bacteroidetes, and Acidobacteria, accounted for about 72% to 87% of total prokaryotic sequences in different BSCs. The most abundant eukaryotic microorganism was Ascomycota, accounting for 47% to 93% of the total eukaryotic sequences. Along the succession of BSCs, the abundance of photoautotrophic Cyanobacteria, Chlorophyta, and Bacillariophyta declined, and that of heterotrophic microorganisms such as bacteria and fungi increased. Statistical analysis showed clear divergency of microbial taxa at the class level among the different successional stages of BSCs. The clustering results at class level showed that the moss crusts were the farthest from the rest in prokaryotic composition; the alga crusts were the most different in terms of eukaryotic microorganisms and the two kinds of lichen crusts were relatively closer in both compositions. Ordination analysis showed that the main variations of community structure among BSCs could be explained best by the abundance of Cyanobacteria and Ascomycota and by physiochemical properties of BSCs, including mechanical composition, moisture, and electrical conductivity. In conclusion, our results indicate that Cyanobacteria and Ascomycota likely play an important role in the evolution of BSC structure and functions and highlight the importance of environmental factors in shaping microbial community structures of BSCs in the Tengger Desert of China.