The hematophagous habits of insects belonging to the genus Lutzomyia (Diptera: Psychodidae), as well as their role as biological vectors of Leishmania species, make their presence an indication of infection risk. In the present study, seven species of Lutzomyia were identified and screened for natural infections with Wolbachia. Collection of sand flies was done in an endemic focus of leishmaniasis on the Colombian Caribbean coast (Department of Sucre, Ovejas municipality). DNA collected from Lutzomyia species was evaluated with PCR for wsp gene amplification to screen for bacterial infection. Endosymbiotic Wolbachia was found in three species: Lutzomyia c. cayennensis, Lutzomyia dubitans and Lutzomyia evansi. Two Wolbachia strains (genotypes) were found in Lutzomyia spp. These genotypes were previously unknown in dipteran insects. The wLev strain was found in Lutzomyia dubitans, L. c. cayennensis and L. evansi and the wLcy strain was found only in L. c. cayennensis. Genetic analysis indicated that the Wolbachia strains wLcy and wLev belong to the B Supergroup. This study provides evidence of infections of more than one strain of Wolbachia in L. c. cayennensis.