Methylomonas methanica MC09 is a mesophilic, halotolerant, aerobic, methanotrophic member of the Gammaproteobacteria, isolated from coastal seawater. Here we present the complete genome sequence of this strain, the first available from an aerobic marine methanotroph.