Wolbachia is a genus of obligate bacterial endosymbionts that infect a diverse range of arthropod species as well as filarial nematodes, with its single described species, Wolbachia pipientis, divided into several ‘supergroups’ based on multilocus sequence typing. Wolbachia strains in mosquitoes have been shown to inhibit the transmission of human pathogens, including Plasmodium malaria parasites and arboviruses. Despite their large host range, Wolbachia strains within the major malaria vectors of the Anopheles gambiae and Anopheles funestus complexes appear at low density, established solely on PCR-based methods. Questions have been raised as to whether this represents a true endosymbiotic relationship. However, recent definitive evidence for two distinct, high-density strains of supergroup B Wolbachia within Anopheles demeilloni and Anopheles moucheti has opened exciting possibilities to explore naturally occurring Wolbachia endosymbionts in Anopheles for biocontrol strategies to block Plasmodium transmission. Here, we utilize genomic analyses to demonstrate that both Wolbachia strains have retained all key metabolic and transport pathways despite their smaller genome size, with this reduction potentially attributable to degenerated prophage regions. Even with this reduction, we confirmed the presence of cytoplasmic incompatibility (CI) factor genes within both strains, with wAnD maintaining intact copies of these genes while the cifB gene was interrupted in wAnM, so functional analysis is required to determine whether wAnM can induce CI. Additionally, phylogenetic analysis indicates that these Wolbachia strains may have been introduced into these two Anopheles species via horizontal transmission events, rather than by ancestral acquisition and subsequent loss events in the Anopheles gambiae species complex. These are the first Wolbachia genomes, to our knowledge, that enable us to study the relationship between natural strain Plasmodium malaria parasites and their anopheline hosts.