Significance A wide range of organisms sense Earth’s magnetic field for navigation. For some organisms, like magnetotactic bacteria, magnetic particles form inside cells and act like a compass. However, the origin of magnetotactic behavior remains a mystery. We report that magnetotaxis evolved in bacteria during the Archean, before or near the divergence between the Nitrospirae and Proteobacteria phyla, suggesting that magnetotactic bacteria are one of the earliest magnetic-sensing and biomineralizing organisms on Earth. The early origin for magnetotaxis would have provided evolutionary advantages in coping with environmental challenges faced by microorganisms on early Earth. The persistence of magnetotaxis in separate lineages implies the temporal continuity of geomagnetic field, and this biological evidence provides a constraint on the evolution of the geodynamo.