Horizontal gene transfer (HGT), the transfer of genetic material other than by descent, is thought to have played significant roles in the evolution and distribution of genes in prokaryotes. These include those responsible for the ability of motile, aquatic magnetotactic bacteria (MTB) to align and swim along magnetic field lines and the biomineralization of magnetosomes that are responsible for this behaviour. There is some genomic evidence that HGT might be responsible for the distribution of magnetosome genes in different phylogenetic groups of bacteria. For example, in the genomes of a number of MTB, magnetosome genes are present as clusters within a larger structure known as the magnetosome genomic island surrounded by mobile elements such as insertion sequences and transposases as well as tRNA genes. Despite this, there is no strong direct proof of HGT between these organisms. Here we show that a phylogenetic tree based on magnetosome protein amino acid sequences from a number of MTB was congruent with the tree based on the organisms' 16S rRNA gene sequences. This shows that evolution and divergence of these proteins and the 16S rRNA gene occurred similarly. This suggests that magnetotaxis originated monophyletically in the Proteobacteria phylum and implies that the common ancestor of all Proteobacteria was magnetotactic.