Under the same selection pressures, two genetically divergent populations may evolve in parallel toward the same adaptive solutions. Here, we hypothesized that magnetotaxis (i.e., magnetically guided chemotaxis) represents a key adaptation to micro-oxic habitats in aquatic sediments and that its parallel evolution homogenized the phenotypes of two evolutionary divergent clusters of freshwater spirilla. All magnetotactic bacteria affiliated to the Magnetospirillum genus (Alphaproteobacteria class) biomineralize the same magnetic particle chains and share highly similar physiological and ultrastructural features. We looked for the processes that could have contributed at shaping such an evolutionary pattern by reconciling species and gene trees using newly sequenced genomes of Magnetospirillum related bacteria. We showed that repeated horizontal gene transfers and homologous recombination of entire operons contributed to the parallel evolution of magnetotaxis. We propose that such processes could represent a more parsimonious and rapid solution for adaptation compared with independent and repeated de novo mutations, especially in the case of traits as complex as magnetotaxis involving tens of interacting proteins. Besides strengthening the idea about the importance of such a function in micro-oxic habitats, these results reinforce previous observations in experimental evolution suggesting that gene flow could alleviate clonal interference and speed up adaptation under some circumstances.