The Egyptian/Phoenician circumnavigation of Africa you refer to is recorded by Herodotus:
For Libya shows clearly that it is encompassed by sea, save only where it borders on Asia; and this was proved first (as far as we know) by Necos king of Egypt. He, when he had made an end of digging the canal which leads from the Nile to the Arabian Gulf, sent Phoenicians in ships, charging them to sail on their return voyage past the Pillars of Heracles till they should come into the northern sea and so to Egypt. So the Phoenicians set out from the Red Sea and sailed the southern sea; whenever autumn came they would put in and sow the land, to whatever part of Libya they might come, and there await the harvest; then, having gathered in the crop, they sailed on, so that after two years had passed, it was in the third that they rounded the Pillars of Heracles and came to Egypt. There they said (what some may believe, though I do not) that in sailing round Libya they had the sun on their right hand.12
Book 4, chapter 42
And there's a footnote by the editor of the 1921 Loeb Classical Edition, from which this translation came:
12The detail which Herodotus does not believe incidentally confirms the story; as the ship sailed west round the cough, the sun of the southern hemisphere would be on its right. Most authorities now accept the story of the circumnavigation.
Historians today don't always take Herodotus at face value. According to livius.org, 2nd Century CE geographer Cladius Ptolemy didn't believe it was possible. The Nile Canal was closed in 767 by Caliph Al-Mansur to put down a rebellion and it silted up. So no other circumnavigation of Africa and only Africa was possible until the Suez Canal opened in 1859.
You can believe Herodotus or not; it's the only chance before 1859.
Except there's a technicality.
In 1519, Ferdinand Magellan set out with 5 ships and 250-270 men. After three years and several mutinies and battles, and much hardship and starvation, a single ship, the Victoria, managed to return to Spain with captain Juan Sebastian Elcano, Italian historian Pigafetta, and 16 others. As a consequence of the first known circumnavigation of the Earth, these guys managed to circumnavigate not only Africa, but also Europe, Asia, and the Americas. That's what happens when you sail a closed loop on the Earth, you're likely to circumnavigate something.
Note: There appear to be some people interpreting a mere passage around the Cape of Good Hope as a "circumnavigation" of Africa. That is clearly not the intent of the OP, and a mischaracterizaton of what the Victoria did. By Sailing all the way around the Earth, Elcano, Pigafetta, and their companions completed a closed loop with Africa inside. That's a circumnavigation.