The film's plot revolves around Asterix and Obelix attempting to complete a series of tough challenges set by Julius Caesar, who seeks to prove they and their fellow villagers are not god.

Although the Gauls nearly succumb to the women, Obelix comes to his senses when he learns that there are no wild boars for him to hunt and eat, allowing the pair to accomplish the challenge.

Following their success in enduring the "Cave of the Beast" in the next challenge, the pair find themselves told by Caius to acquire a permit document from "The Place that Sends you Mad", a multi-storey bureaucratic building.

After finding it impossible because of the clinically unhelpful people who direct them elsewhere, Asterix beats them at their own game by requesting an imaginary permit and turning their behaviour against them, resulting in the building's Prefect to unwittingly hand over what the Gauls came for.

The pair continue to complete further challenges: crossing a ravine filled with crocodiles by beating them up rather than using an invisible tightrope; answering a riddle by the Old Man of the Mountain, conducted in the form of a washing detergent advertisemen; and enduring a night on a plain haunted by ghostly legionnaires, who Asterix scares away through furious complaints.