But now a Greek expedition, led by archaeologist Liana Souvaltzis of the Athens-based Institute of Hellenistic Studies, has found what appears to be Alexander's tomb - not in Alexandria, but in the middle of the desert at the oasis of Siwa, 330 miles south west of the city.
In front of the tomb - a huge, 160 ft-long stone structure - the archaeologists unearthed three stone inscriptions, each of which appear to refer to Alexander, while inside the building at the entrance to a series of three chambers they found, inscribed on masonry, an eight-pointed star - the symbol of Alexander's Macedonian royal family.
The tomb itself is built on classic Macedonian lines, but is substantially bigger than any of the royal tombs in ancient Macedonia itself.
Siwa was the site of one of the ancient world's three great sacred oracles, along with Delphi and Dodona, both in Greece. The Siwa oracular temple was the home of the Egyptian ram god Ammon.
To Alexander, Siwa was the most important place in the world. He believed himself to be Ammon's son and consulted his divine "father" there before setting off on his campaigns. And before his death in 323BC he made it known that he wished to be buried there.
The oasis certainly became a centre for the worship of Alexander, for even as late as the 5th century AD, it is known that the Roman Empire's by then Christian authorities had to suppress a Cult of Alexander which was flourishing in Siwa.
What's more the ancient name for Siwa - Santariya - is thought to derive from a variant of the name Alexander, while the hills overlooking the tomb are still known locally as the Jebel Sekunder (the Mountains of Alexander). But if, as now seems likely, Alexander was buried in Siwa, can this new discovery be squared with the ancient accounts which state categorically that he was laid to rest in Alexandria?
The answer is yes - but it means rewriting the history books. The ancient sources are agreed on three facts: first, that Alexander died in Babylon; second, that his corpse (presumably mummified) was kept for a period in the Egyptian capital Memphis; and third, that at some stage, sooner or later (depending on which ancient source one reads), his body was taken to Alexandria. All three facts are almost certainly correct - but with one important addition. A re-reading of the ancient texts in the light of the new find suggests that the mummified corpse was probably taken to Siwa only after it had been kept "in storage" for 10 to 15 years in Memphis and before being transferred much later to Alexandria.
Major military problems - not least a Persian invasion of Egypt - could well have been responsible for the delay in implementing Alexander's wish to be interred in his divine father's oasis. One of the newly discovered inscriptions - both thought to bethe work of Alexander's successor as ruler of Egypt, Ptolemy I - sheds light on this.
It reads: "I present these sacrifices according to the orders of the god and carried the corpse here - and it was so light, as light as a small shield - when I was Commander of Egypt.
"It was I who was caring about his secrets, and who was carrying out his wishes. And I was honest to him and to all people and as I am the last one still alive I hereby state that I have done all the above for his sake."
It is likely that Alexander's body stayed at Siwa for around 100 years - that is until the accession to power in Egypt of one of the world's most debauched rulers.
Ptolemy IV, who loved orgies and married his sister, became unpopular with the masses and needed the corpse of the long-dead and divine Alexander as a sort of political icon to boost his flagging fortunes. Accordingly he built a special temple in which the mummified body of Alexander the God was put, Lenin-like, on display.
It must therefore have been at this stage and for this purpose that Alexander's body was shifted from Siwa to Alexandria.
There is however one final mystery. In the time of Ptolemy IV, no one would have known exactly what Alexander had looked like. So the degenerate monarch could easily have put virtually any old mummy in the temple and got away with it, without having to disturb Alexander in Siwa.
So, having found what appears to have been Alexander's tomb, the archaeologists could conceivably still unearth his body. The search continues.