The parasite Trypanosoma brucei rhodesiense and its insect vector Glossina morsitans morsitans were used to evaluate the effect of parasite clearance (resistance) as well as the cost of midgut infections on tsetse host fitness. Tsetse flies are viviparous and have a low reproductive capacity, giving birth to only 6-8 progeny during their lifetime. Thus, small perturbations to their reproductive fitness can have a major impact on population densities. We measured the fecundity (number of larval progeny deposited) and mortality in parasite-resistant tsetse females and untreated controls and found no differences. There was, however, a typanosome-specific impact on midgut infections. Infections with an immunogenic parasite line that resulted in prolonged activation of the tsetse immune system delayed intrauterine larval development resulting in the production of fewer progeny over the fly's lifetime. In contrast, parasitism with a second line that failed to activate the immune system did not impose a fecundity cost. Coinfections favored the establishment of the immunogenic parasites in the midgut. We show that a decrease in the synthesis of Glossina Milk gland protein (GmmMgp), a major female accessory gland protein associated with larvagenesis, likely contributed to the reproductive lag observed in infected flies. Mathematical analysis of our empirical results indicated that infection with the immunogenic trypanosomes reduced tsetse fecundity by 30% relative to infections with the non-immunogenic strain. We estimate that a moderate infection prevalence of about 26% with immunogenic parasites has the potential to reduce tsetse populations. Potential repercussions for vector population growth, parasite-host coevolution, and disease prevalence are discussed.