Microcoleus vaginatus plays a prominent role as both primary producer and pioneer in biocrust communities from dryland soils. And yet, it cannot fix dinitrogen, essential in often nitrogen-limited drylands. But a diazotroph-rich "cyanosphere" has been described in M. vaginatus, hinting that there exists a C for N exchange between the photoautotroph and heterotrophic diazotrophs. We provide evidence for this by establishing such a symbiosis in culture and by showing that it is selective and dependent on nitrogen availability. In natural populations, provision of nitrogen resulted in loss of diazotrophs from the cyanosphere of M. vaginatus compared to controls, but provision of phosphorus did not. Co-culturing of pedigreed cyanosphere diazotroph isolates with axenic M. vaginatus resulted in copious growth in C and N-free medium, but co-culture with non-cyanosphere diazotrophs or other heterotrophs did not. Unexpectedly, bundle formation in M. vaginatus, diacritical to the genus but not seen in axenic culture, was restored in vitro by imposed nitrogen limitation or, even more strongly, by co-culture with diazotrophic partners, implicating this trait in the symbiosis. Our findings provide direct evidence for a symbiotic relationship between M. vaginatus and its cyanosphere and help explain how it can be a global pioneer in spite of its genetic shortcomings.