Genetic-modification strategies are currently being developed to reduce the transmission of vector-borne diseases, including African trypanosomiasis. For tsetse, the vector of African trypanosomiasis, a paratransgenic strategy is being considered: this approach involves modification of the commensal symbiotic bacteria Sodalis to express trypanosome-resistance-conferring products. Modified Sodalis can then be driven into the tsetse population by cytoplasmic incompatibility (CI) from Wolbachia bacteria. To evaluate the effectiveness of this paratransgenic strategy in controlling African trypanosomiasis, we developed a three-species mathematical model of trypanosomiasis transmission among tsetse, humans, and animal reservoir hosts. Using empirical estimates of CI parameters, we found that paratransgenic tsetse have the potential to eliminate trypanosomiasis, provided that any extra mortality caused by Wolbachia colonization is low, that the paratransgene is effective at protecting against trypanosome transmission, and that the target tsetse species comprises a large majority of the tsetse population in the release location. Author Summary: African sleeping sickness is a fatal disease occurring in sub-Saharan Africa. The parasites that cause African sleeping sickness are transmitted between humans and livestock by the tsetse fly. Controlling the spread of the parasite by tsetse flies has been proposed as a promising strategy for reducing the incidence of sleeping sickness. One potential control method relies on releasing genetically modified tsetse that are resistant to carrying the sleeping sickness parasite. For this strategy to be successful, resistant tsetse must be able to invade the susceptible tsetse population. Here, we used a mathematical model to assess the feasibility of such a strategy and the implications for sleeping sickness prevalence in humans and livestock. We found that the strategy has the potential to eliminate sleeping sickness, provided that the genetic modification is effective at protecting against trypanosome transmission and provided that the target tsetse species comprises a large majority of the tsetse population in the release location.