A common feature of microbial colonization in deserts is biological soil crusts (BSCs), and these comprise a complex community dominated by Cyanobacteria. Rock substrates, particularly sandstone, are also colonized by microbial communities. These are separated by bare sandy soil that also supports microbial colonization. Here we report a high-throughput sequencing study of BSC and cryptoendolith plus adjacent bare soil communities in the Colorado Plateau Desert, Utah, USA. Bare soils supported a community with low levels of recoverable DNA and high evenness, whilst BSC yielded relatively high recoverable DNA, and reduced evenness compared to bare soil due to specialized crust taxa. The cryptoendolithic community displayed the greatest evenness but the lowest diversity, reflecting the highly specialized nature of these communities. A strong substrate-dependent pattern of community assembly was observed, and in particular cyanobacterial taxa were distinct. Soils were virtually devoid of photoautotrophic signatures, BSC was dominated by a closely related group of Microcoleus/Phormidium taxa, whilst cryptoendolithic colonization in sandstone supported almost exclusively a single genus, Chroococcidiopsis. We interpret this as strong evidence for niche filtering of taxa in communities. Local inter-niche recruitment of photoautotrophs may therefore be limited and so communities likely depend significantly on cyanobacterial recruitment from distant sources of similar substrate. We discuss the implication of this finding in terms of conservation and management of desert microbiota.