The story focuses on Asterix and Obelix accompanying their village's druid, Getafix, to Ancient Egypt, in order to help an artitect friend of his complete a major construction project that will allow Cleopatra to win a bet against Julius Caesar.

Infuriated, Cleopatra, queen of the greek, Ptolemaic Kingdom, makes a wager with him that she can prove that they are still great by having a grand palace constructed in Alexandria within three months.

To handle the construction project, Cleopatra assigns Edifis, a man who claims to be the best architect in her kingdom, to build the palace, promising to reward him greatly with gold, but warns he will be fed to the sacred crocodiles of the Nile if he fails.

Concerned with the task he has been given, Edifis decides to travel to Armorica in Gaul, in order to request aid from his old friend Getafix, a druid who supplies his village with a magic potion that gives them superhuman strength to resist the Romans.

When he returns, Mintjulep explains about the presence of the Gauls and their magic potion, which prompts Caesar to order several of his legions to assault the construction site and capture them.

Construction is eventually completed on time, much to Cleopatra's delight, allowing Edifis to be rewarded with gold; he and Artifis also reconcile their differences and agree to work together on future projects.