Nitrogen fixation rates of the globally distributed, biogeochemically important marine cyanobacterium Trichodesmium increase under high carbon dioxide (CO2) levels in short-term studies due to physiological plasticity. However, its long-term adaptive responses to ongoing anthropogenic CO2 increases are unknown. Here we show that experimental evolution under extended selection at projected future elevated CO2 levels results in irreversible, large increases in nitrogen fixation and growth rates, even after being moved back to lower present day CO2 levels for hundreds of generations. This represents an unprecedented microbial evolutionary response, as reproductive fitness increases acquired in the selection environment are maintained after returning to the ancestral environment. Constitutive rate increases are accompanied by irreversible shifts in diel nitrogen fixation patterns, and increased activity of a potentially regulatory DNA methyltransferase enzyme. High CO2-selected cell lines also exhibit increased phosphorus-limited growth rates, suggesting a potential advantage for this keystone organism in a more nutrient-limited, acidified future ocean.