Sand fly and Leishmania are one of the best studied vector-parasite models. Much is known about the development of these parasites within the sand fly, and how transmission to a suitable vertebrate host takes place. Various molecules secreted by the vector assist the establishment of the infection in a vertebrate, and changes to the vector are promoted by the parasites in order to facilitate or enhance transmission. Despite a generally accepted view that sand flies and Leishmania are also one of the oldest vector-pathogen pairs known, such long history has not been translated into a harmonic relationship. Leishmania are faced with many barriers to the establishment of a successful infection within the sand fly vector, and specific associations have been developed which are thought to represent aspects of a co-evolution between the parasite and its vectors. In this review, we highlight the journey taken by Leishmania during its development within the vector, and describe the issues associated with the natural barriers encountered by the parasite. Recent data revealed sexual replication of Leishmania within the sand fly, but it is yet unknown if such reproduction affects disease outcome. New approaches targeting sand fly molecules to prevent parasite transmission are being sought, and various techniques related to genetic manipulation of sand flies are being utilized.