An understanding of the taxonomic status and vector distribution of anophelines is crucial in controlling malaria. Previous phylogenetic analyses have supported the description of six species of the Neotropical malaria vector Anopheles (Nyssorhynchus) albitarsis s.l. (Diptera: Culicidae): An. albitarsis, Anopheles deaneorum, Anopheles marajoara, Anopheles oryzalimnetes, Anopheles janconnae and An. albitarsis F. To evaluate the taxonomic status of An. albitarsis s.l. mosquitoes collected in various localities in the Colombian Caribbean region, specimens were analyzed using the complete mitochondrial DNA cytochrome oxidase I (COI) gene, the ribosomal DNA (rDNA) internal transcribed spacer 2 (ITS2) region and partial nuclear DNA white gene sequences. Phylogenetic analyses of the COI gene sequences detected a new lineage closely related to An. janconnae in the Caribbean region of Colombia and determined its position relative to the other members of the complex. However, the ITS2 and white gene sequences lacked sufficient resolution to support a new lineage closely related to An. janconnae or the An. janconnae clade. The possible involvement of this new lineage in malaria transmission in Colombia remains unknown, but its phylogenetic closeness to An. janconnae, which has been implicated in local malaria transmission in Brazil, is intriguing.