Strains of a pink-pigmented Methylobacterium sp. are effective nitrogen- (N2) fixing microsymbionts of species of the African crotalarioid genus Listia. Strain WSM2598 is an aerobic, motile, Gram-negative, non-spore-forming rod isolated in 2002 from a Listia bainesii root nodule collected at Estcourt Research Station in South Africa. Here we describe the features of Methylobacterium sp. WSM2598, together with information and annotation of a high-quality draft genome sequence. The 7,669,765 bp draft genome is arranged in 5 scaffolds of 83 contigs, contains 7,236 protein-coding genes and 18 RNA-only encoding genes. This rhizobial genome is one of 100 sequenced as part of the DOE Joint Genome Institute 2010 Genomic Encyclopedia for Bacteria and Archaea–Root Nodule Bacteria (GEBA-RNB) project.