It is generally accepted that Alexandria ad Aegyptum was founded ex nihilo in 331 BC by Alexander the Great, rapidly growing into one of antiquity's most opulent economic and intellectual centers. However, ancient texts by Strabo (17.1.6) and Pliny (NH 5.11.62) suggest the existence of a pre-Hellenistic settlement named Rhakotis. This literary evidence has fuelled contentious scholarly debate for decades. Here we present new geochemical data from Alexandria's ancient bay sediments, elucidating unequivocal proof for pollutant lead (Pb) input into the harbor during the Egyptian Old Kingdom (2686--2181 BC). A second contamination peak is detected during the Iron Age (1000--800 BC), at the end of the prosperous Ramesses reigns. These findings evidence thriving pre-Hellenistic settlements in Alexandria. During the Greek and Roman periods, we expound the largest Pb pollution ever encountered in ancient city sediments with Pb levels twice as high as those measured in contemporary industrialized estuaries.