The application of tattoos to the human body has enjoyed a long and diverse history in many ancient cultures. At present, the oldest surviving examples are the mainly geometric tattoos on the individual known as Ötzi, dating to the late 4th millennium BCE, whose skin was preserved by the ice of the Tyrolean Alps. In the Egyptian Nile valley, the arid climate has also promoted extensive soft tissue preservation. Here we report on the tattoos found during the examination of two of the best preserved naturally mummified bodies from Egypt’s Predynastic (c. 4000-3100 BCE) period, making them the earliest extant examples from the Nile Valley. Figural tattoos that mirror motifs found in Predynastic art were observed on the right arm of one male and the right arm and shoulder of one female, demonstrating conclusively that tattooing was practiced in prehistoric Egypt. These findings overturn the circumstantial evidence of the artistic record that previously suggested only females were tattooed for fertility or even erotic reasons. Radiocarbon testing and datable iconographic parallels for the motifs indicate that these tattooed individuals are nearly contemporaneous with the Iceman, positioning them amongst the bearers of some of the oldest preserved tattoos in the world. At over five thousand years of age, they push back the evidence for tattooing in Africa by a millennium and provide new insights into the range of potential uses of tattoos in pre-literate societies by both sexes, revealing new contexts for exploring the visual language of prehistoric times.