Global warming will likely force terrestrial plant and animal species to migrate toward cooler areas or sustain range losses; whether this is also true for microorganisms remains unknown. Through continental-scale compositional surveys of soil crust microbial communities across arid North America, we observed a latitudinal replacement in dominance between two key topsoil cyanobacteria that was driven largely by temperature. The responses to temperature of enrichment cultures and cultivated strains support this contention, with one cyanobacterium (Microcoleus vaginatus) being more psychrotolerant and less thermotolerant than the other (M. steenstrupii). In view of our data and regional climate predictions, the latter cyanobacterium may replace the former in much of the studied area within the next few decades, with unknown ecological consequences for soil fertility and erodibility.