The genetic background of the European Mesolithic and the extent of population replacement during the Neolithic is poorly understood, both due to the scarcity of human remains from that period 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. 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). 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.