After a heated argument with Julius Caesar over his lack of faith in the Egyptian people, Queen Cleopatra enters into a bet claiming that she can have a magnificent palace constructed for him in Alexandria within three months.

His scheming rival Amonbofis proposes that they collaborate in order to build Caesar's palace on time and divide the reward between them; the catch being that Numerobis alone be thrown to the crocodiles should they fail.

Building progress becomes so rapid that the labourers exhaust their supplies of stone; Amonbofis has bribed the supplier to dump the subsequent shipment into the Nile and the Gauls are forced to escort a fleet of ships to fetch more.

Undeterred, Amonbofis and Krukhut make a further attempt to prevent the stone reaching its destination by hiring the same gang of pirates seen earlier in the film to attack the fleet on its return to Alexandria.

In a final effort to stop the three Gauls, Amonbofis frames them for an attempt to poison Cleopatra with the gift of a cake made from such ingredients as arsenic, strychnine and vitriol.

Panoramix carries an antidote that enables them to eat the remainder of the cake (giving the impression that it was in fact harmless) as well as curing the taster after claiming he has indigestion.

Cleopatra gloats over the likelihood of winning her bet to Caesar, who fears he will lose face with her should she get the better of him and instructs his spy to infiltrate the building site.

Learning that the Gauls and their magic potion are involved, Caesar orders his three mercenaries, brothers, to kidnap Panoramix and knock over the cauldron for which they will receive a bag of gold.