Insecticide resistance poses a growing challenge to malaria vector control. Following evidence of associations between the mosquito microbiota and insecticide resistance, we characterized the microbial composition of malaria vectors in relation to their insecticide resistance profiles, in different locations with high and low levels of pyrethroid resistance. Here, we report findings from our study on Anopheles gambiae s.s. in Turukuyi village, Bungoma County, where high levels of pyrethroid resistance were detected. F1 non-blood fed female An. gambiae s.s. that were obtained from wild-caught mosquitoes were exposed to five times (107.5µg/ml) the discriminating dose of permethrin using the CDC bottle bioassay. The microbiota of mosquitoes that were alive (resistant, n=50) or dead (susceptible, n=50) following the bioassay were characterized using high throughput sequencing targeting the universal bacterial and archaeal 16S rRNA gene. Results showed significant differences in bacterial composition between resistant and susceptible individuals (PERMANOVA, F=2.33, P=0.001), with Sphingobacterium and Streptococcus—both comprising pyrethroid-degrading species, and the radiotolerant Rubrobacter, being over three folds (P<0.05) more abundant in resistant compared to susceptible mosquitoes. This first report of association between the microbiota and pyrethroid resistance in An. gambiae s.s. corroborates results of previous studies conducted on Anopheles albimanus from Peru and Guatemala. Our findings form the basis of future work on the role of mosquito microbiota in insecticide resistance, and potentially the identification of novel microbial markers of insecticide resistance in mosquito populations.