The arrival of Europeans in Colonial and post-Colonial times coupled with the forced introduction of sub-Saharan Africans have dramatically changed the genetic background of Venezuela. The main aim of the present study was to evaluate, through the study of mitochondrial DNA (mtDNA) variation, the extent of admixture and the characterization of the most likely continental ancestral sources of present-day urban Venezuelans. We analyzed two admixed populations that have experienced different demographic histories, namely, Caracas (n = 131) and Pueblo Llano (n = 219). The native American component of admixed Venezuelans accounted for 80% (46% haplogroup [hg] A2, 7% hg B2, 21% hg C1, and 6% hg D1) of all mtDNAs; while the sub-Saharan and European contributions made up ∼10% each, indicating that Trans-Atlantic immigrants have only partially erased the native American nature of Venezuelans. A Bayesian-based model allowed the different contributions of European countries to admixed Venezuelans to be disentangled (Spain: ∼38.4%, Portugal: ∼35.5%, Italy: ∼27.0%), in good agreement with the documented history. Seventeen entire mtDNA genomes were sequenced, which allowed five new native American branches to be discovered. B2j and B2k, are supported by two different haplotypes and control region data, and their coalescence ages are 3.9 k.y. (95% C.I. 0-7.8) and 2.6 k.y. (95% C.I. 0.1-5.2), respectively. The other clades were exclusively observed in Pueblo Llano and they show the fingerprint of strong recent genetic drift coupled with severe historical consanguinity episodes that might explain the high prevalence of certain Mendelian and complex multi-factorial diseases in this region.