Wild Japanese macaques (Macaca fuscata Blyth) living in the highland and lowland areas of Yakushima are known to have different diets, with highland individuals consuming more leaves. We aim to clarify whether and how these differences in diet are also reflected by gut microbial composition and fermentation ability. Therefore, we conduct an in vitro fermentation assay using fresh feces from macaques as inoculum and dry leaf powder of Eurya japonica Thunb. as a substrate. Fermentation activity was higher for feces collected in the highland, as evidenced by higher gas and butyric acid production and lower pH. Genetic analysis indicated separation of highland and lowland in terms of both community structure and function of the gut microbiota. Comparison of feces and suspension after fermentation indicated that the community structure changed during fermentation, and the change was larger for lowland samples. Analysis of the 16S rRNA V3-V4 barcoding region of the gut microbiota showed that community structure was clearly clustered between the two areas. Furthermore, metagenomic analysis indicated separation by gene and pathway abundance patterns. Two pathways (glycogen biosynthesis I and D-galacturonate degradation I) were enriched in lowland samples, possibly related to the fruit-eating lifestyle in the lowland. Overall, we demonstrated that the more leaf-eating highland Japanese macaques harbor gut microbiota with higher leaf fermentation ability compared with the more fruit-eating lowland ones. Broad, non-specific taxonomic and functional gut microbiome differences suggest that this pattern may be driven by a complex interplay between many taxa and pathways rather than single functional traits.