The primary succession history of magnetotactic bacteria (MTB) is reconstructed in postglacial lake sediments using a rock magnetic approach that discriminates biologically produced magnetite from nonorganic magnetic carriers. MTB are among the oldest prokaryotes found in the fossil record, but little is known about how they have colonized and recolonized habitats around the world. Here we observe how MTB synchronously colonized 4 freshwater lakes 9760 ± 160 yr ago. The lakes are more than 1400 km apart, representing both coastal and inland regions, and have altitudinal differences of almost 800 m. The synchronous colonization of Norway (and possibly Sweden) suggests that the pathways were extremely efficient, and that the sources must have been wide ranging. We propose that birds could have carried and spread the bacteria as northward migration routes were reestablished following the onset of the current interglacial. This unique data set underscores the tenacity of MTB as evolutionary survivors, and also demonstrates their response to large-scale environmental changes in ways not previously anticipated.