Potash mining, typically performed for agricultural fertilizer production, can create piles of residual salt waste that are ecologically detrimental and difficult to revegetate. Biological soil crusts (biocrusts) have been found growing on and around these heaps, suggesting resilience to the hypersaline environment. We set out to understand the community dynamics of biocrust formation by examining two succesionary salinity gradients at historical mining sites using a high throughput amplicon sequencing. Bare heaps were distinct, with little overlap between sites, and were characterized by high salinity, low nutrient availability, and specialized, low diversity microbial communities, dominated by Halobacteria, Chloroflexia, and Deinococci. 'Initial' stages of biocrust development were dominated by site-specific Cyanobacteria, with significant overlap between sites. Established biocrusts were the most diverse, with large proportions of Alphaproteobacteria, Anaerolineae, and Planctomycetacia. Along the salinity gradient at both sites, salinity decreased, pH decreased, and nutrients and Chlorophyll a increased. Microbiomes between sites converged during succession and community assembly process analysis revealed biocrusts at both sites were dominated by deterministic, niche-based processes; indicating a high degree of phylogenetic turnover. We posit early cyanobacterial colonization is essential for biocrust initiation, and facilitates later establishment of plant and other higher-level biota.