Magnetotactic bacteria (MTB) are a heterogeneous group of aquatic prokaryotes with a unique intracellular organelle, the magnetosome, which orients the cell along magnetic field lines. Magnetotaxis is a complex phenotype, which depends on the coordinate synthesis of magnetosomes and the ability to swim and orient along the direction caused by the interaction with the Earth's magnetic field. Although a number of putative magnetotaxis genes were recently identified within a conserved genomic magnetosome island (MAI) of several MTB, their functions have remained mostly unknown, and it was speculated that additional genes located outside the MAI might be involved in magnetosome formation and magnetotaxis. In order to identify genes specifically associated with the magnetotactic phenotype, we conducted comparisons between four sequenced magnetotactic Alphaproteobacteria including the nearly complete genome of Magnetospirillum gryphiswaldense strain MSR-1, the complete genome of Magnetospirillum magneticum strain AMB-1, the complete genome of the magnetic coccus MC-1, and the comparative-ready preliminary genome assembly of Magnetospirillum magnetotacticum strain MS-1 against an in-house database comprising 426 complete bacterial and archaeal genome sequences. A magnetobacterial core genome of about 891 genes was found shared by all four MTB. In addition to a set of approximately 152 genus-specific genes shared by the three Magnetospirillum strains, we identified 28 genes as group specific, i.e., which occur in all four analyzed MTB but exhibit no (MTB-specific genes) or only remote (MTB-related genes) similarity to any genes from nonmagnetotactic organisms and which besides various novel genes include nearly all mam and mms genes previously shown to control magnetosome formation. The MTB-specific and MTB-related genes to a large extent display synteny, partially encode previously unrecognized magnetosome membrane proteins, and are either located within (18 genes) or outside (10 genes) the MAI of M. gryphiswaldense. These genes, which represent less than 1% of the 4,268 open reading frames of the MSR-1 genome, as yet are mostly of unknown functions but are likely to be specifically involved in magnetotaxis and, thus, represent prime targets for future experimental analysis.