Królowa Egiptu, Kleopatra, ma dość szyderstw Juliusza Cezara, związanych ze zmierzchem cywilizacji egipskiej. Obiecuje Cezarowi, że w trzy miesiące wybuduje mu w Aleksandrii pałac; jeśli jej się to powiedzie, Cezar będzie musiał przyznać, że Egipt wciąż rośnie w siłę, a jego lud jest genialny.
Kleopatra powierza budowę pałacu architektowi Numerobisowi, w razie sukcesu obiecując mu złoto, a w razie klęski – rzucenie krokodylom na pożarcie. Architekt, świadomy, że sam nie poradzi sobie z tym zadaniem, udaje się do wioski Galów, by prosić o pomoc druida Panoramiksa.
Galijski kapłan zgadza się wesprzeć Numerobisa. W towarzystwie Asteriksa, Obeliksa i Idefiksa ruszają do Egiptu, gdzie będą musieli zmierzyć się z zakusami zarówno Rzymian, jak i Egipcjan[3].
Idefiks (fr. Idéfix) – Asteriks i Kleopatra jest pierwszym komiksem serii, w której piesek Obeliksa otrzymuje swoje imię i gdzie odgrywa większą rolę, ratując bohaterów z zamknięcia w piramidzie[4],
Numerobis (fr. Numérobis) – najlepszy architekt w Aleksandrii; wyznaczony przez Kleopatrę do budowy pałacu Cezara[5],
Piramidonis (fr. Amonbofis) – architekt z Aleksandrii; gdy Numerobis odmawia mu współpracy przy budowie pałacu, Piramidonis przysięga Numerobisowi zemstę[6],
Kleopatra (fr. Cléopâtre) – królowa Egiptu; jej spór z Juliuszem Cezarem staje się przyczyną nowej przygody wojowniczych Galów[7].
Elizabeth Taylor jako tytułowa bohaterka filmu Kleopatra.Goscinny i Uderzo wpadli na pomysł stworzenia komiksu po obejrzeniu filmu KleopatraJosepha L. Mankiewicza z 1963 r.; znalazło to swoje odzwierciedlenie między innymi w postaci Kleopatry, przypominającej Elizabeth Taylor w roli władczyni Egiptu[7],
w komiksie kilkukrotnie zwraca się uwagę na nos Kleopatry (np. w obecnym we wstępie tekście: Pałac legendarnej królowej Kleopatry. To właśnie o jej nosie powiedziano, że gdyby był krótszy inaczej wyglądałoby oblicze świata[8]). Źródłem tych uwag jest aforyzm Blaise’a Pascala: Nos Kleopatry: gdyby był trochę krótszy, cała powierzchnia ziemi wyglądałaby inaczej[9][10],
skryba Numerobisa, Brudnopis, nawiązuje do egipskiej rzeźby Siedzący skryba[11].