As an obligate dietary specialist feeding almost exclusively on the foliage of a single plant genus, Eucalyptus, the koala (Phascolarctos cinereus) is a rarity amongst mammals. The koala has a particularly large hindgut and slow gut passage rate, accommodating a gastrointestinal microbiome that assists in digestion of this diet, which is physically tough, nutritionally poor, high in fibre and defended by digestibility-reducing tannins and numerous toxins. Using 16S amplicon sequencing followed by a gene-centric analysis of whole-community shotgun sequencing data, we characterized the gastrointestinal microbiomes of 20 koalas from a single geographic location but with two contrasting diets: Eucalyptus viminalis, a highly-preferred species that supports unsustainable rates of koala population growth, and Eucalyptus obliqua, a less-preferred species with low koala densities. E. viminalis has more protein and digestible protein than E. obliqua and lower tannin and fibre concentrations, and a different suite of defence compounds. Of the two diets, E. viminalis produced microbiomes with fewer bacterial species and less diversity which were dominated by the bacterial genera Parabacteroides and Bacteroides (Phyum Bacteroidetes) rather than by genera from the family Ruminococcacea (Phylum Firmicutes). We highlight likely microbiome functional differences identified from catalytic and carbohydrate-binding enzyme abundances associated with oligo- and polysaccharide degradation from the CAZy database, and potentially active metabolic pathways identified from the KEGG database. These differences highlight the close association between the koala, its diet and its symbiotic gut microbes and raise the question, can specialized microbial communities further narrow the nutritional niche of their dietary specialist hosts?