Traditional theories on ancient Egyptian mummification postulate that in the prehistoric period (i.e. the Neolithic and Chalcolithic periods, 5th and 4th millennia B.C.) bodies were naturally desiccated through the action of the hot, dry desert sand. Although molding of the body with resin-impregnated linen is believed to be an early Pharaonic forerunner to more complex processes, scientific evidence for the early use of resins in artificial mummification has until now been limited to isolated occurrences during the late Old Kingdom (c. 2200 B.C.), their use becoming more apparent during the Middle Kingdom (c. 2000-1600 BC). We examined linen wrappings from bodies in securely provenanced tombs (pit graves) in the earliest recorded ancient Egyptian cemeteries at Mostagedda in the Badari region (Upper Egypt). Our investigations of these prehistoric funerary wrappings using a combination of gas chromatography-mass spectrometry (GC-MS) and thermal desorption/pyrolysis (TD/Py)-GC-MS have identified a pine resin, an aromatic plant extract, a plant gum/sugar, a natural petroleum source, and a plant oil/animal fat in directly AMS-dated funerary wrappings. Predating the earliest scientific evidence by more than a millennium, these embalming agents constitute complex, processed recipes of the same natural products, in similar proportions, as those utilized at the zenith of Pharaonic mummification some 3,000 years later. The antibacterial properties of some of these ingredients and the localized soft-tissue preservation that they would have afforded lead us to conclude that these represent the very beginnings of experimentation that would evolve into the famous mummification practice of the Pharaonic period.