Sodalis glossinidius, a maternally inherited secondary symbiont of the tsetse fly, is a bacterium in the early/intermediate state of the transition toward symbiosis, representing an important model for investigating establishment and evolution of insect–bacteria symbiosis. The absence of phylogenetic congruence in tsetse-Sodalis coevolution and the existence of Sodalis genotypic diversity in field flies are suggestive for a horizontal transmission route. However, to date no natural mechanism for the horizontal transfer of this symbiont has been identified. Using novel methodologies for the stable fluorescent-labeling and introduction of modified Sodalis in tsetse flies, we unambiguously show that male-borne Sodalis is 1) horizontally transferred to females during mating and 2) subsequently vertically transmitted to the progeny, that is, paternal transmission. This mixed mode of transmission has major consequences regarding Sodalis’ genome evolution as it can lead to coinfections creating opportunities for lateral gene transfer which in turn could affect the interaction with the tsetse host.