Epidemiological studies typically focus on single-parasite systems, although most hosts harbor multiple parasite species; thus, the potential impacts of co-infection on disease dynamics are only beginning to be recognized. Interactions between macroparasites, such as gastrointestinal nematodes, and microparasites causing diseases like TB, AIDS, and malaria are particularly interesting because co-infection may favor transmission and progression of these important diseases. Here we present evidence for strong interactions between gastrointestinal worms and bovine tuberculosis (TB) in free-ranging African buffalo (Syncerus caffer). TB and worms are negatively associated at the population, among-herd, and within-herd scales, and this association is not solely the result of demographic heterogeneities in infection. Combining data from 1362 buffalo with simple mechanistic models, we find that both accelerated mortality of co-infected individuals and TB transmission heterogeneity caused by trade-offs in immunity to the two types of parasites likely contribute to observed infection patterns. This study is one of the first to examine the relevance of within-host immunological trade-offs for understanding parasite distribution patterns in natural populations.