The genetic background of the European Mesolithic and the extent of population replacement during the Neolithic 1–10 is poorly understood, both due to the scarcity of human remains from that period 11–18 and the inherent methodological difficulties of ancient DNA research. However, advances in sequencing technologies are both increasing data yields and providing supporting evidence for data authenticity, such as nucleotide misincorporation patterns 19–22. We use these methods to characterize both the mitochondrial DNA genome and generate shotgun genomic data from two exceptionally well-preserved 7,000-year-old Mesolithic individuals from La Braña-Arintero site in León (Northwestern Spain) 23. The mitochondria of both individuals are assigned to U5b2c1, a haplotype common among the small number of other previously studied Mesolithic individuals from Northern and Central Europe. This suggests a remarkable genetic uniformity and little phylogeographic structure over a large geographic area of the pre-Neolithic populations. Using Approximate Bayesian Computation, a model of genetic continuity from Mesolithic to Neolithic populations is poorly supported. Furthermore, analyses of 1.34% and 0.53% of their nuclear genomes, containing about 50,000 and 20,000 ancestry informative SNPs, respectively, show that these two Mesolithic individuals are not related to current populations from either the Iberian Peninsula or Southern Europe. ► The first complete Mesolithic mtDNA genome retrieved ► There is a remarkable genetic uniformity in Europe during the Mesolithic period ► Modern Iberians are not direct descendants of the 7,000-year-old hunter-gatherers ► Genetic discontinuity between Mesolithic/Neolithic populations supported by simulations