According to Julius Caesar, Admiral Crustacius is "The silliest sausage in Rome" - he's lost Caesar's personal galley to its own slaves. "The galley slaves are revolting..." "And so are you! Stop beefing!" Caesar warns Crustacius to retrieve the galley or be in dire straits, a promise the admiral passes to his vice-admiral.
The slaves, led by Spartakis the Greek, need a place where they can live free from Roman oppression, and on the advice of a British slave, decide to sail to a village by the coast of Armorica. According to his uncle Anticlimax, the Indomitable Gauls are able to bash the Romans with their magic potion.
At Asterix's village, the Gauls notice that the Legionaries of the four fortified camps are gathering, and assume they're going to attack. Luckily, Getafix has already prepared two cauldrons of Magic Potion, though just one will be enough. As usual, Obelix is denied any, and when the Gauls go out to thump the Romans, he's not part of the battle. It turns out Vice-Admiral Nautilus was just preparing a parade to welcome Admiral Crustacius, but gets thumps anyway. Obelix's absence worried Asterix, and Getafix soon realizes what happened. Rushing back to the village, the druid finds that Obelix has drunk the second cauldron of Magic Potion, and turned to stone as a result of potion overdose!
While Getafix tries to find a cure for Obelix's condition, Crustacius meets with Nautilus at Aquarium and they discuss their plans to re-capture Caesar's galley. The Roman fleet has been following the galley at a distance, and the mutineers will undoubtedly try to take refuge in the Gaulish Village. The plan is to take the ship back after the slaves leave it. But when Spartakis asks the Gauls for refuge, the Gauls use their Magic Potion to carry the entire ship into the village!
Meanwhile, Obelix has finally recovered from his stony state - and returned to childhood! And no one is more upset about this than Obelix, as he has no super-strength, and so can't lift menhirs and only has enough appetite for a less than a single boar. Getafix refuses to try anything, as Obelix has undergone too many changes as is. Obelix decides to go live in the forest and bumps into a troop of Legionaries led by Nautilus. The vice-admiral was looking a Gaulish hostage, and decides that Obelix will do. As a child, Obelix can't bash the Romans like he wants to and is captured. Dogmatix runs back to the village for help, and leads Asterix and company to Aquarium. They bash the camp up, but Crustacius has already taken Obelix on his ship, planning to use the young Gaul as a bargaining chip to get Caesar's galley.
Asterix and the slaves set out to sea on Caesar's galley, with Getafix accompanying. The druid has had a brainstorm on a way to fix Obelix's condition, and brings a barrel of Magic Potion along with Asterix's typical gourd. They soon catch up with Crustacius' galley, sinking the Pirates by accident, and rescue Obelix. To make up to the Pirates, Asterix gives them Caesar's galley and Crustacius and Nautilus, so the Pirates can collect a ransom from Caesar.
Sailing on Crustacius' ship, Getafix names their next destination - Atlantis! Though the main continent sank ages ago, some lesser islands remain, believed now to be the Canary Islands. Along the way, Asterix realizes that they left the barrel of magic potion on Caesar's galley. Arriving on Atlantis, our heroes find that it is inhabited by children, human and centaur, save the High Priest Absolutelifabulos. The Atlanteans have figured out the secret of eternal youth, but to the Gauls' distress, not the secret of aging. However, Spartakis and his group decide to stay, and the Gauls leave, wishing them luck.
Meanwhile, as Caesar's galley nears Rome, Crustacius gets a taste of magic potion. After throwing the Pirates overboard, he decides he wants to take Rome from Caesar. But first, he'd better make sure Nautilus doesn't get any potion...
With the Gauls, their ship is attacked by another Roman galley. Before Asterix can drink some magic potion, a catapult shot knocks him out, sending his gourd into the sea. Legionaries board the ship, and with Getafix overboard to retrieve the gourd, there's nothing to stop them from throwing Asterix to the sharks. The sight of his friend in danger is too much for Obelix, and he wills himself back to his original state. With his adulthood and strength returned, Obelix makes quick work of the Romans, just as Getafix climbs back aboard.
At Rome, Nautilus finds Crustacius - or his stone body, as the Admiral drank the rest of the barrel containing Magic Potion. Rome's coastal guard, seeing a pirate flag, has the galley sunk, learning only too late that it belonged to Caesar. In the end, Nautilus and the trigger-happy coast guards are made sweepers of the Colosseum. Crustacius' stone body is put in the Colosseum's center, "In memory of the silliest Sausage in Rome." Caesar hopes that the lions will someday develop a taste for granite, to the confusion of Cleopatra.
The Gauls return to Armorica, though with Obelix's strength they row the galley right through Aquarium. The Gauls have their ending feast, with Obelix chowing down on boars to make up for lost time.
- Atlantis: Asterix, Obelix, Getafix and the galley slaves visit the remains of the continent in an attempt to find a cure for Obelix, and the slaves decide to stay there.
- Call-Back: The British slave who inspired Spartakis to head to Armorica is the nephew of Asterix's second cousin (once removed) Anticlimax.
- Dude, Not Funny!: In-universe; when a Hurricane of Puns follows Obelix's stone-state, Asterix furiously demands that they show a little respect.
- Fountain of Youth: Atlanteans know the secret of eternal youth, and as such all inhabitants are children except for the high priest. Unfortunately for the Gauls, they don't know anything about aging, and thus can't help Obelix.
- I Gave My Word: Caesar promised he'd feed Crustacius to the lions if he failed to recover his galley. Crustacius becoming a statue didn't stop him.
- Made a Slave: After the Pirates are given Caesar's galley so they can return it to Rome, they force Admiral Crustacius and Vice-Admiral Nautilus to join the rowers.
- National Stereotypes: The galley slaves comprise a Briton, Belgian, Greek, Mauretanian, German and Hispaniard (Spaniard).
- Named After Somebody Famous: Spartakis is named after Spartacus.
- No Celebrities Were Harmed: The face of Spartakis is modelled after Kirk Douglas.
- O.O.C. Is Serious Business: When Obelix, who is usually a Blood Knight, doesn't take part in the thrashing of the assembled Roman Legions, Asterix and Getafix soon realize that something must have happened.
- Shout-Out: Spartakis is a shout-out to Spartacus, of course. The flying cows and horses on Atlantis are a Homage to Fantasia.
- Slave Liberation: What starts the album.
- Taken for Granite: Drinking too much Magic Potion in one go will turn the drinker to stone. In a unique variation, clothes are not transformed.