The book begins with an argument between Cleopatra, Queen of Egypt, and Julius Caesar, in which Caesar belittles the accomplishments of the Egyptian people. Infuriated, Cleopatra makes a wager with Caesar promising to build a new palace in Alexandria within three months. Cleopatra summons Edifis, who claims to be the best architect in Egypt. She promises Edifis that if he builds the palace on time he will be covered with gold; if he fails, he will be a meal for the sacred crocodiles.
A worried Edifis thinks he needs magic to help him, enlists the help of the Gauls, Asterix, Obelix, Getafix, and Dogmatix. Thanks to Getafix and his magic potion, the work goes forward on schedule, despite multiple attempts by Edifis's arch rival, Artifis, to sabotage the construction after Edifis says he doesn't want his help, claiming Artifis works people too hard. Artifis tells the workers to demand less whipping, which would slow construction. However Getafix gives the workers magic potion. Artifis bribes the stone-delivery man to throw his load away, before Obelix beats him up, causing him to reveal the truth, a henchman tries to lock the Gauls inside a pyramid but Dogmatix helps them find their way out, he tries to frame the Gauls by sending a poisoned cake to Cleopatra, but Getafix makes an antidote enabling the Gauls to eat it, then cures the taster and claims eating too much rich food was giving him a bad stomach. Edifis is kidnapped and hidden in a sarcophagus in the house of Artifis, but Obelix frees him. Artifis and his henchman are forced to work on the palace, but without magic potion.
Just before the palace is due to be completed, Caesar intervenes by sending legions to try to arrest the Gauls, after he realises the three Gauls are in Egypt when a spy disguises himself as a worker, and sees the effects of the magic potion. The Gauls fight off the Roman soldiers, but the commanding officer proceeds to shell the building with his catapults. In desperation, Asterix and Dogmatix deliver the news to Cleopatra. A furious Cleopatra then hurries to the construction site to berate Caesar. Caesar's legions are ordered to fix the damage they caused (without any magic potion to help them) and the palace is successfully completed on time. Cleopatra wins her bet and covers Edifis with gold. Edifis and Artifis reconcile and agree to build pyramids together, and Cleopatra gives Getafix some papyrus manuscripts from the Library of Alexandria as a gift. The Gauls return, but Vitalstatistix criticises Obelix trying to give an Egyptian style point to menhirs.