Lutzomyia spp. are New World phlebotomine sand flies, many of which are involved in the transmission of human diseases, such as leishmaniases and bartonellosis. The systematic classification of the approximately 400 species in the genus has been based on morphological characters, but the relationships within the genus are still very much in question. We have inferred phylogenies of 32 species of phlebotomine sand flies belonging to seven sub-genera and two species groups, by using fragments of the mitochondrial small subunit (12SrRNA) and of the nuclear large subunit (28SrRNA) ribosomal gene sequences. The subgenus Helcocyrtomyia and the Verrucarum species group, prominent representatives of the Peruvian sand fly fauna, were represented by 11 and 7 species, respectively. Although based on a limited number of taxa, the resulting phylogenies, based on 837 characters, provide an initial phylogenetic backbone for the progressive reconstruction of infrageneric relationships within Lutzomyia.