Methylomicrobium strains are widespread in saline environments. Here, we report the complete genome sequence of Methylomicrobium alcaliphilum 20Z, a haloalkaliphilic methanotrophic bacterium, which will provide the basis for detailed characterization of the core pathways of both single-carbon metabolism and responses to osmotic and high-pH stresses. Final assembly of the genome sequence revealed that this bacterium contains a 128-kb plasmid, making M. alcaliphilum 20Z the first methanotrophic bacterium of known genome sequence for which a plasmid has been reported.