Juliusz Cezar przybywa z wizytą do Aleksandrii i swej ukochanej Kleopatry. Między królewską parą dochodzi do sporu, czyj naród jest potężniejszy. Oburzona pychą Cezara Kleopatra zakłada się, że w trzy miesiące wybuduje wspaniały pałac na jego cześć i tym samym udowodni mu nieustająca wielkość Aleksandrii i jej mieszkańców. Cezar bez namysłu zgadza się na zakład, pewien, że Kleopatra przegra. Królowa powierza to karkołomne zadanie najlepszemu w Aleksandrii architektowi, Numerobisowi. Jeśli mu się nie powiedzie, zostanie rzucony krokodylom na pożarcie. Numerobis jest załamany i choć nie wierzy w sukces, przystępuje do budowy. Gdy w Aleksandrii zjawiają się dzielni Galowie – Asteriks i Obeliks – plan budowy pałacu zyskuje szansę powodzenia…