Social corbiculate bees such as honey bees and bumble bees maintain a specific beneficial core microbiome which is absent in wild bees. It has been suggested that maintaining this microbiome can prevent disease and keep bees healthy. The main aim of our study was to identify if there are any core bacterial groups in the non-corbiculate bees Ceratina and Megalopta that have been previously overlooked. We additionally test for associations between the core bee microbes and pollen provisions to look for potential transmission between the two. We identify three enterotypes in Ceratina samples, with thirteen core bacterial phylotypes in Ceratina females: Rosenbergiella, Pseudomonas, Gilliamella, Lactobacillus, Caulobacter, Snodgrassella, Acinetobacter, Corynebacterium, Sphingomonas, Commensalibacter, Methylobacterium, Massilia, and Stenotrophomonas, plus 19 in pollen (6 of which are shared by bees). Unlike Apis bees, whose gut microbial community differs compared to their pollen, Ceratina adults and pollen largely share a similar microbial composition and enterotype difference was largely explained by pollen age. Megalopta displays a highly diverse composition of microbes throughout all adults, yet Lactobacillus and Saccharibacter were prevalent in 90% of adults as core bacteria. Only Lactobacillus was both a core bee and pollen provision microbe in all three species. The consequences of such diversity in core microbiota between bee genera and their associations with pollen are discussed in relation to identifying potentially beneficial microbial taxa in wild bees to aid the conservation of wild, understudied, non-model bee species.