The book begins with a now familiar scene of the indomitable Gauls' village. Asterix and Obelix are setting off for a wild boar hunt when they pass a beautiful blond young lady by the name of Panacea who has been picking mushrooms. She has returned to the village after studying in Condatum. Obelix immediately falls in love. After a few scenes of Obelix embarrassing himself, Panacea receives word that her fiancé Tragicomix has been conscripted into the Roman army and shipped to North Africa. Asterix and Obelix promise Panacea that they will return Tragicomix to her, even though it breaks Obelix's heart.
Asterix and Obelix head for Condatum where they learn that Tragicomix has already left for Massilia, the Mediterranean port from which the soldiers depart. They then decide to enlist in the Roman army and end up training with Allegoric, a Goth; Selectivemploymentax, a Briton; Gastronomix, a Belgian; Neveratalos, a Greek; and Ptenisnet, an Egyptian tourist who spends the entire book believing himself to be in a holiday camp.
After completing training (which is rather relaxing for the conscripts while very stressful for the Centurions), the newly formed unit sets off as reinforcements to Caesar who is fighting a losing campaign against a rival Roman faction headed by Caecilius Metellus Scipio in alliance with Afranius and King Juba I of Numidia. Asterix and Obelix soon find out that Tragicomix has gone missing in action after a skirmish.
Asterix and Obelix desert and set out to search for him, raiding Scipio's camp and successfully rescuing the young man. However, due to their actions Caesar and Scipio each believes that the other is attacking and they both prepare for battle. In the confusion that follows, Caesar achieves a great victory (the historical Battle of Thapsus, 46 BC). The Gauls are cornered by Caesar, but released and sent home for the service they provided — Panacea is reunited with Tragicomix and everybody is overjoyed.
In gratitude, Panacea kisses both Asterix and Obelix. Obelix faints and Asterix spends the customary banquet sitting on a tree hopelessly in love, as well.
The book features a number of recurring jokes.
- This is the first Asterix book in which either Asterix or Obelix shows any interest in women, and whenever any of the characters breaks down in tears, someone always remarks "In love, is he?" Panacea's kisses reduce grown men to simpering weaklings: she tames the jealous and antagonistic Dogmatix, knocks down the unstoppable Obelix, and leaves a smitten Asterix sitting out the final banquet in a love-struck daze.
- Obelix regularly refers to bashing Romans as "being polite," following an incident when Asterix recommended that behaviour but then ended up using violence.
The Roman legionaries in Asterix's unit are all comic stereotypes of various nations.
- the hair of the Belgian legionary resembles that of the Belgian comic character Tintin;
- the Egyptian speaks only in hieroglyphics, and when giving his appreciation for the accommodation (he thinks the barracks is a hotel), he says them in the style of Michelin Guide-style icons, such as stars, houses, and forks-and-knives;
- the Goths speak in a Gothic script font;
- the Greek says "by Zeus" a lot and speaks in a Greek-style font;
- just as in Asterix in Britain the notoriously terrible British cuisine is referenced, when the British recruit is the only one to appreciate the horrible food served at mealtime at the Roman garrison.
When the pirates are first sunk, the ship's remains parody the 19th century painting The Raft of the Medusa. In the English version, the pirate captain even exclaims "We've been framed, by Jericho!", a pun on the artist Géricault.
Throughout the story the Egyptian makes comments in hieroglyphics about hairy body parts — this is based on child's game in France that involves repeating back a rhyme of whatever was last said in the form of "old hairy (body part)."