African trypanosomes are insect-borne parasites that cause sleeping sickness in humans and nagana in domesticated animals. Successful transmission is the outcome of crosstalk between the trypanosome and its insect vector, the tsetse fly. This enables the parasite to undergo successive rounds of differentiation, proliferation and migration, culminating in the infection of a new mammalian host. Several stage- and species-specific parasite surface molecules have been identified and there are new insights into their regulation in the fly. Tsetse flies are often refractory to infection with trypanosomes. While many environmental and physiological factors are known to influence infection, our detailed understanding of tsetse-trypanosome relationships is still in its infancy. Recent studies have identified a number of tsetse genes that show altered expression patterns in response to microbial infections, some of which have also been implicated in modulating trypanosome transmission.