All animals harbor beneficial microbes, and one way these microbes can benefit their animal hosts is by increasing the diversity and efficacy of communication signals available to them. The symbiotic hypothesis for mammalian chemical communication posits that bacteria in the specialized scent glands of mammals generate odorous metabolites used by their hosts for communication, and that variation in host chemical signals is, in large part, a product of underlying variation in the bacterial communities inhabiting these glands. An effective test of this hypothesis would require accurate surveys of the bacterial communities in mammals’ scent glands and complementary data on the odorant profiles of scent secretions—both of which have been historically lacking. We used next-generation sequencing technologies to deeply survey bacterial communities in the scent glands of wild spotted and striped hyenas. We showed that these communities were dominated by odor-producing, fermentative bacteria, and that the structures of these communities covaried with the volatile fatty acid profiles of scent secretions in both hyena species. The bacterial and odor profiles of secretions differed between spotted and striped hyenas and, controlled for social group, both profiles varied with sex and reproductive state among spotted hyenas. These results strongly support the symbiotic hypothesis for chemical communication, suggesting that symbiotic bacteria underlie species-specific odors in both spotted and striped hyenas, and underlie sex and reproductive state-specific odors among spotted hyenas. These results suggest that symbiotic bacteria are critical contributors to hyenas’ signaling phenotypes, and that they are therefore important mediators in the complex social lives of hyenas.