Desulfovibrio africanus strain Walvis Bay is an anaerobic sulfate-reducing bacterium (SRB) capable of producing methylmercury (MeHg), a potent human neurotoxin. The mechanism of methylation by this and other organisms is unknown. We present the 4.2 Mb genome sequence to provide further insight into microbial mercury methylation and sulfate-reducing bacteria.