The central rift of the Red Sea contains 25 brine pools with different physicochemical conditions, dictating the diversity and abundance of the microbial community. Three of these pools, the Atlantis II, Kebrit and Discovery Deeps, are uniquely characterized by a high concentration of hydrocarbons. The brine-seawater interface, described as an anoxic-oxic (brine-seawater) boundary, is characterized by a high methane concentration, thus favoring aerobic methane oxidation. The current study analyzed the aerobic free-living methane-oxidizing bacterial communities that potentially contribute to methane oxidation at the brine-seawater interfaces of the three aforementioned brine pools, using metagenomic pyrosequencing, 16S rRNA pyrotags and pmoA library constructs. The sequencing of 16S rRNA pyrotags revealed that these interfaces are characterized by high microbial community diversity. Signatures of aerobic methane-oxidizing bacteria were detected in the Atlantis II Interface (ATII-I) and the Kebrit Deep Upper (KB-U) and Lower (KB-L) brine-seawater interfaces. Through phylogenetic analysis of pmoA, we further demonstrated that the ATII-I aerobic methanotroph community is highly diverse. We propose four ATII-I pmoA clusters. Most importantly, cluster 2 groups with marine methane seep methanotrophs, and cluster 4 represent a unique lineage of an uncultured bacterium with divergent alkane monooxygenases. Moreover, non-metric multidimensional scaling (NMDS) based on the ordination of putative enzymes involved in methane metabolism showed that the Kebrit interface layers were distinct from the ATII-I and DD-I brine-seawater interfaces.