Intraspecific niche divergence is an important driver of species range, population abundance, and impacts on ecosystem functions. Genetic changes are the primary focus when studying intraspecific divergence; however, the role of ecological interactions, particularly host-microbiome symbioses, is receiving increased attention. The relative importance of these evolutionary and ecological mechanisms has seen only limited evaluation. To address this question, we used Microcystis aeruginosa, the globally-distributed cyanobacterium that dominates freshwater harmful algal blooms. These blooms have been increasing in occurrence and intensity worldwide, causing major economic and ecological damages. We evaluated 46 isolates of M. aeruginosa and their microbiomes, collected from 14 lakes in Michigan, USA that vary over 20-fold in phosphorus levels, the primary limiting nutrient in freshwater systems. Genomes of M. aeruginosa diverged along this phosphorus gradient in genomic architecture and protein functions. Fitness in low-phosphorus lakes corresponded with additional shifts within M. aeruginosa including genome-wide reductions in nitrogen use, an expansion of phosphorus assimilation genes, and an alternative life history strategy of non-clonal colony formation. In addition to host shifts, despite culturing in common garden conditions, host-microbiomes diverged along the gradient in taxonomy, but converged in function with evidence of metabolic interdependence between the host and its microbiome. Divergence corresponded with a physiological tradeoff between fitness in low-phosphorus environments and growth rate in phosphorus-rich conditions. Co-occurrence of genotypes adapted to different nutrient environments in phosphorus-rich lakes may have critical implications for understanding how M. aeruginosa blooms persist after initial nutrient depletion. Ultimately, we demonstrate that the intertwined effects of genome evolution, host life history strategy, and ecological interactions between a host and its microbiome correspond with an intraspecific niche shift with important implications for whole ecosystem function. This article is protected by copyright. All rights reserved.