The mechanisms that underpin the varied spatial genetic structures exhibited by free-living marine microorganisms remain controversial, with most studies emphasizing a high dispersal capability that should redistribute genetic diversity in contrast to most macroorganisms whose populations often retain a genetic signature of demographic response to historic climate fluctuations. We quantified the European phylogeographic structure of the marine flagellate Oxyrrhis marina and found a marked difference in spatial genetic structure, population demography, and genetic diversity between the northwest Atlantic and Mediterranean Sea that reflects the persistent separation of these regions as well as context-dependent population responses to contrasting environments. We found similar geographic variation in the level of genetic diversity in the sister species Oxyrrhis maritima. Because the capacity for wide dispersal is not always realized, historic genetic footprints of range expansion and contraction persist in contemporary populations of marine microbes, as they do in larger species. Indeed, the well-described genetic effects of climatic variation on macroorganisms provide clear, testable hypotheses about the processes that drive genetic divergence in marine microbes and thus about the response to future environmental change.