Because Africa's climate hampers DNA preservation, knowledge of its genetic variability is mainly restricted to modern samples, even though population genetics dynamics and back-migrations from Eurasia may have modified haplotype frequencies, masking ancient genetic scenarios. Thanks to improved methodologies, ancient genetic data for the African continent are now increasingly available, starting to fill in the gap. Here we present newly obtained mitochondrial genomes from two ~7000-year-old individuals from Takarkori rockshelter, Libya, representing the earliest and first genetic data for the Sahara region. These individuals carry a novel mutation motif linked to the haplogroup N root. Our result demonstrates the presence of an ancestral lineage of the N haplogroup in the Holocene "Green Sahara", associated to a Middle Pastoral (Neolithic) context.