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.