Magnetotactic bacteria (MTB) are a phylogenetically diverse group which uses intracellular membrane-enclosed magnetite crystals called magnetosomes for navigation in their aquatic habitats. Although synthesis of these prokaryotic organelles is of broad interdisciplinary interest, its genetic analysis has been restricted to a few closely related members of the Proteobacteria, in which essential functions required for magnetosome formation are encoded within a large genomic magnetosome island. However, because of the lack of cultivated representatives from other phyla, it is unknown whether the evolutionary origin of magnetotaxis is monophyletic, and it has been questioned whether homologous mechanisms and structures are present in unrelated MTB. Here, we present the analysis of the uncultivated "Candidatus Magnetobacterium bavaricum" from the deep branching Nitrospira phylum by combining micromanipulation and whole genome amplification (WGA) with metagenomics. Target-specific sequences obtained by WGA of cells, which were magnetically collected and individually sorted from sediment samples, were used for PCR screening of metagenomic libraries. This led to the identification of a genomic cluster containing several putative magnetosome genes with homology to those in Proteobacteria. A variety of advanced electron microscopic imaging tools revealed a complex cell envelope and an intricate magnetosome architecture. The presence of magnetosome membranes as well as cytoskeletal magnetosome filaments suggests a similar mechanism of magnetosome formation in "Cand. M. bavaricum" as in Proteobacteria. Altogether, our findings suggest a monophyletic origin of magnetotaxis, and relevant genes were likely transferred horizontally between Proteobacteria and representatives of the Nitrospira phylum.