Microbes that synthesize minerals, a process known as microbial biomineralization, contributed substantially to the evolution of current planetary environments through numerous important geochemical processes. Despite its geological significance, the origin and evolution of microbial biomineralization remain poorly understood. Through combined metagenomic and phylogenetic analyses of deep-branching magnetotactic bacteria from the Nitrospirae phylum, and using a Bayesian molecular clock-dating method, we show here that the gene cluster responsible for biomineralization of magnetosomes, and the arrangement of magnetosome chain(s) within cells, both originated before or near the Archean divergence between the Nitrospirae and Proteobacteria. This phylogenetic divergence occurred well before the Great Oxygenation Event. Magnetotaxis likely evolved due to environmental pressures conferring an evolutionary advantage to navigation via the geomagnetic field. Earth’s dynamo must therefore have been sufficiently strong to sustain microbial magnetotaxis in the Archean, suggesting that magnetotaxis coevolved with the geodynamo over geological time.