The sugarcane aphid (Melanaphis sacchari (Zehntner), SCA) was first reported on sugarcane in the continental USA in Florida in 1977 and in Louisiana in 1999. In 2013 SCA abruptly became a serious pest of sorghum and is currently a sorghum pest in twenty-two states across the continental USA. The insect microbiome is known to play an important role in allowing populations of an insect species to consume different host plants. Therefore, we assessed whether changes in microbiota composition may explain the SCA outbreak in USA sorghum. Samples were collected from Louisiana before the 2013 pest outbreak and from four states (Alabama, Florida, Louisiana, Texas) after 2014. We characterized the SCA bacterial microbiota on sugarcane and grain sorghum, using taxon-specific PCR primers and a metabarcoding approach. All SCA harbored Buchnera aphidicola. Interestingly, none of the facultative bacteria typically associated with aphids (e.g., Arsenophonus, Hamiltonella, Regiella) were present in either the PCR screens or metabarcoding data. However, metabarcoding detected bacteria not previously identified in aphids (e.g., Arcobacter, Bifidobacterium, Citrobacter, etc.). Lastly, we found microbial host-associated differentiation in aphids that seems to correspond to the genetically distinct aphid lineages that prefer to feed on grain sorghum (MLL-F) and sugarcane (MLL-D). With this foundation of the SCA microbiota, we can assess the role that these microbes may play in pest status of SCA. In addition, we can use the presence of these microbes to refine and develop Integrated Pest Management (IPM) techniques against SCA.