Human African trypanosomiasis (HAT), transmitted by tsetse flies, has historically infected hundreds of thousands of individuals annually in sub-Saharan Africa. Over the last decade, concerted control efforts have reduced reported cases to below 10,000 annually, bringing complete elimination within reach. A potential technology to eliminate HAT involves rendering the flies resistant to trypanosome infection. This approach can be achieved through the introduction of transgenic Sodalis symbiotic bacteria that have been modified to produce a trypanocide, and propagated via Wolbachia symbionts, which confer a reproductive advantage to the paratransgenic tsetse. However, the population dynamics of these symbionts within tsetse flies have not yet been evaluated. Specifically, the key factors that determine the effectiveness of paratransgenesis have yet to be quantified. To identify the impact of these determinants on T.b. gambiense and T.b. rhodesiense transmission, we developed a mathematical model of trypanosome transmission that incorporates tsetse and symbiont population dynamics. We found that fecundity and mortality penalties associated with Wolbachia or recombinant Sodalis colonization, probabilities of vertical transmission, and tsetse migration rates are fundamental to the feasibility of HAT elimination. For example, we determined that HAT elimination could be sustained over 25 years when Wolbachia colonization minimally impacted fecundity or mortality, and when the probability of recombinant Sodalis vertical transmission exceeded 99.9%. We also found that for a narrow range of recombinant Sodalis vertical transmission probability (99.9-90.6% for T.b. gambiense and 99.9-85.8% for T.b. rhodesiense), cumulative HAT incidence was reduced between 30% and 1% for T.b. gambiense and between 21% and 3% for T.b. rhodesiense, although elimination was not predicted. Our findings indicate that fitness and mortality penalties associated with paratransgenic symbionts, as well as tsetse migration rates, are instrumental to HAT elimination, and should be a key focus in the development of paratransgenic symbionts.