We studied prokaryotic community structure and composition in biological soil crusts (BSCs) from the Sonoran Desert, and their variability over space and time, using statistically analyzed, PCR-based molecular surveys of environmental 16S rRNA genes. Four sites, tens of km apart, were sampled, 3 times over a 1 year period, collecting 10 duplicate samples every 50 m in each site. Denaturing gradient gel electrophoresis (DGGE) revealed communities much less diverse than those of typical soil assemblages, displaying dominance of some bacterial types. No differences in crust microbial diversity or composition were detected between crusts under plant canopies and those in plant interspaces, indicating a likely crust independence from higher plant resources. However, statistically significant variability with space and time could be detected, and samples within a site were more similar than samples between sites. Both temporal and spatial variability in community composition involved non-dominant members of the community. Extensive sequencing and phylogenetic analysis revealed a large array of bacterial types, many novel. The most common included members of Cyanobacteria, Proteobacteria, Actinobacteria and Acidobacteria. Bacteriodetes, Chloroflexi and Gemmatimonadetes were not seen in high numbers, but were present in all sites, and Deinococci were also detected. Archaea were present, but as minor components. Sonoran BSC communities were distinct in rough compositional character from those in bulk arid soils or agricultural soils, and contained reoccurring, uncultured microbes.