The molecular phylogenetic relationships and population structure of the species of the Anopheles triannulatus complex: Anopheles triannulatus s.s., Anopheles halophylus and the putative species Anopheles triannulatus C were investigated. The mitochondrial COI gene, the nuclear white gene and rDNA ITS2 of samples that include the known geographic distribution of these taxa were analyzed. Phylogenetic analyses were performed using Bayesian inference, Maximum parsimony and Maximum likelihood approaches. Each data set analyzed septely yielded a different topology but none provided evidence for the seption of An. halophylus and An. triannulatus C, consistent with the hypothesis that the two are undergoing incipient speciation. The phylogenetic analyses of the white gene found three main clades, whereas the statistical parsimony network detected only a single metapopulation of Anopheles triannulatus s.l. Seven COI lineages were detected by phylogenetic and network analysis. In contrast, the network, but not the phylogenetic analyses, strongly supported three ITS2 groups. Combined data analyses provided the best resolution of the trees, with two major clades, Amazonian (clade I) and trans-Andean + Amazon Delta (clade II). Clade I consists of multiple subclades: An. halophylus + An. triannulatus C; trans-Andean Venezuela; central Amazonia + central Bolivia; Atlantic coastal lowland; and Amazon delta. Clade II includes three subclades: Panama; cis-Andean Colombia; and cis-Venezuela. The Amazon delta specimens are in both clades, likely indicating local sympatry. Spatial and molecular variance analyses detected nine groups, corroborating some of subclades obtained in the combined data analysis. Combination of the three molecular markers provided the best resolution for differentiation within An. triannulatus s.s. and An. halophylus and C. The latest two species seem to be very closely related and the analyses performed were not conclusive regarding species differentiation. Further studies including new molecular markers would be desirable to solve this species status question. Besides, results of the study indicate a trans-Andean origin for An. triannulatus s.l. The potential implications for malaria epidemiology remain to be investigated.