Tsetse flies are vectors of the protozoan parasite African trypanosomes, which cause sleeping sickness disease in humans and nagana in livestock. Although there are no effective vaccines and efficacious drugs against this parasite, vector reduction methods have been successful in curbing the disease, especially for nagana. Potential vector control methods that do not involve use of chemicals is a genetic modification approach where flies engineered to be parasite resistant are allowed to replace their susceptible natural counterparts, and Sterile Insect technique (SIT) where males sterilized by chemical means are released to suppress female fecundity. The success of genetic modification approaches requires identification of strong drive systems to spread the desirable traits and the efficacy of SIT can be enhanced by identification of natural mating incompatibility. One such drive mechanism results from the cytoplasmic incompatibility (CI) phenomenon induced by the symbiont Wolbachia. CI can also be used to induce natural mating incompatibility between release males and natural populations. Although Wolbachia infections have been reported in tsetse, it has been a challenge to understand their functional biology as attempts to cure tsetse of Wolbachia infections by antibiotic treatment damages the obligate mutualistic symbiont (Wigglesworthia), without which the flies are sterile. Here, we developed aposymbiotic (symbiont-free) and fertile tsetse lines by dietary provisioning of tetracycline supplemented blood meals with yeast extract, which rescues Wigglesworthia-induced sterility. Our results reveal that Wolbachia infections confer strong CI during embryogenesis in Wolbachia-free (Gmm(Apo)) females when mated with Wolbachia-infected (Gmm(Wt)) males. These results are the first demonstration of the biological significance of Wolbachia infections in tsetse. Furthermore, when incorporated into a mathematical model, our results confirm that Wolbachia can be used successfully as a gene driver. This lays the foundation for new disease control methods including a population replacement approach with parasite resistant flies. Alternatively, the availability of males that are reproductively incompatible with natural populations can enhance the efficacy of the ongoing sterile insect technique (SIT) applications by eliminating the need for chemical irradiation.