Insect-symbiont interactions are known to play key roles in host functions and fitness. The common insect endosymbiont Wolbachia can reduce the ability of several human pathogens, including arboviruses and the malaria parasite, to replicate in insect hosts. Wolbachia does not naturally infect Aedes aegypti, the primary vector of dengue virus, but transinfected Ae. aegypti have anti-dengue virus properties and are currently being trialled as a dengue biocontrol strategy. Here, we assess the impact of Wolbachia infection of Ae. aegypti on the microbiome of wild mosquito populations (adults and larvae) collected from release sites in Cairns, Australia, by profiling 16S rRNA gene using next generation sequencing. Our data indicate that Wolbachia reduces the relative abundance of a large proportion of bacterial taxa in Ae. aegypti adults, that is in accordance with the known pathogen-blocking effects of Wolbachia on a variety of bacteria and viruses. In adults, several of the most abundant bacterial genera were found to undergo significant shifts in relative abundance. However, the genera showing the greatest changes in relative abundance in Wolbachia-infected adults represented a low proportion of the total microbiome. In addition, there was little effect of Wolbachia infection on the relative abundance of bacterial taxa in larvae, or on species diversity (accounting for species richness and evenness together) detected in adults or larvae. These results offer insight into the effects of Wolbachia on the Ae. aegypti microbiome in a native setting, an important consideration for field releases of Wolbachia into the population.