Gastrointestinal helminth-microbiota associations are shaped by various ecological processes. The effect of the ecological context of the host on the bacterial microbiome and gastrointestinal helminth parasites has been tested in a number of ecosystems and experimentally. This study takes the important step to look at these two groups at the same time and to start to examine how these communities interact in a changing host environment. Fresh faecal samples (N = 335) from eight wild Eulemur populations were collected over 2 years across Madagascar. We used 16S ribosomal RNA gene sequencing to characterise the bacterial microbiota composition, and faecal flotation to isolate and morphologically identify nematode eggs. Infections with nematodes of the genera Callistoura and Lemuricola occurred in all lemur populations. Seasonality significantly contributed to the observed variation in microbiota composition, especially in the dry deciduous forest. Microbial richness and Lemuricola spp. infection prevalence were highest in a previously intensely logged site, whereas Callistoura spp. showed no such pattern. In addition, we observed significant correlations between gastrointestinal parasites and bacterial microbiota composition in these lemurs, with 0.4–0.7% of the variation in faecal bacterial microbiota composition being explained by helminth infections. With this study, we show effects of environmental conditions on gastrointestinal nematodes and bacterial interactions in wild lemurs and believe it is essential to consider the potential role of microbiome-parasite associations on the hosts’ GI stability, health, and survival.