The twenty-second Asterix book opens on a Viking ship sailing through thick fog, helmed by would-be explorer Herendethelessen. One of his crewmates expresses scepticism about the voyage, but Herendethelessen declares that soon, "Yøu'll åll find øut I'm right!"
Meanwhile, in the Gaulish village, an enraged Vitalstatistix confronts Unhygienix the fishmonger about the rotten fish he sold to the chief's shield bearers, who are both ill with food poisoning. Unhygienix explains that the latest shipment of fish from Lutetia is delayed by an ox-cart drivers' strike over the price of hay;note a taunt from Fulliautomatix soon causes a fight to break out (to the amusement of a nearby Roman patrol). As the dust settles from the fight, Asterix asks Unhygienix why he can't just fish in the sea near the village; the offended fishmonger answers that his fish is top quality bought from Lutetian wholesalers, not just any old fish out of the sea, and they'll just have to wait for the next delivery. However, Getafix says he needs reasonably fresh fish to make the magic potion, and stocks are so low that he can't afford to wait. Asterix, Obelix, and Dogmatix volunteer to go fishing, taking Geriatrix's old fishing boat and a gourd of magic potion. The skies are clouding over as they push out to sea.
The fishing voyage goes badly from the start; when Asterix tells Obelix to throw out the fishing net, the latter doesn't bother attaching it to anything first, and when they try to return to the village for another net, the brewing storm drives them further out to sea. They are forced to spend the night in the boat in the hope that the weather will improve, and, apart from a close encounter with Herendethelessen and his fellow Vikings' ship, the night passes without incident and they wake to find the seas and wind completely calm. However, the storm has blown them so far out to sea that there is no land in sight, and with no wind, they're stuck where they are.
Obelix is now getting hungry; fortunately, Dogmatix spots the ship of Redbeard and his pirate crew on the horizon, and, as luck would have it, they have a huge feast on board for the captain's birthday. The food is commandeered by Obelix, but, in a display of generosity, Asterix leaves the pirates a single sausage for the festivities; Obelix devours the entire feast in minutes except for an apple. Another storm drives the boat still further out to sea, and with just the apple and rainwater to sustain them, Obelix becomes delirious with hunger and jumps overboard. Asterix jumps after him, and the boat is carried off without them; luckily, Obelix finds a branch to hold onto, a sure sign that land is near.
When they reach land, Obelix assumes they have returned home, but a discovery of three strange (but delicious) gobbling birds and a bear, wildlife not native to their part of Gaul, soon puts paid to that theory. They decide to sleep on the question of where they have landed, unaware that they are being watched by the natives. After they wake from their short nap, Dogmatix picks up the scent of one of the natives; Obelix assumes they must be Romans, but gets into an argument with Asterix over the need for stealth - an argument ended by an arrow landing between them. As they try to find the bowman who fired it, one of the natives distracts Obelix with a turkey call, and as he runs off, Asterix is knocked out by a tomahawk and taken prisoner.
Obelix, meanwhile, finds the native making the turkey calls and knocks him out by shaking him out of the tree in which he is hiding. As he tries to find Asterix again, he finds only his helmet, and has Dogmatix use the scent to lead him to the native village, where he finds Asterix tied to a post while the natives dance around him to the sound of drumbeats. After Asterix is untied, he and Obelix continue to speculate on the nationality of the natives and try to surmount the Language Barrier with a display of mime which only confuses the tribal chief. However, when they are each challenged to a fight by members of the tribe, their strength impresses the chief and he invites them to stay.
The Gauls continue to impress the natives during a hunting trip, an account of which is painted onto an animal skin and given to them as a present. The chief is so delighted by their strength that he decides to engage his daughter to Obelix. Alarmed at being pushed into an Arranged Marriage, Obelix persuades Asterix that they should start for home again, and they sneak away by night in one of the tribe's canoes - which happens to have a hole in the bottom, ensuring they don't get far. They swim to a nearby island and spend the night there.
The next morning, Herendethelessen's crew are getting increasingly fed up with the voyage, which we finally learn is in search of a new world which the captain believes lies many miles west of their homeland. The crew are threatening to return to Denmark when Herendethelessen's dog, Huntingseassen, spots the island on which Asterix and Obelix have spent the night. The Gauls see the ship, and Asterix signals to them by standing on a heap of stones while carrying the animal skin and holding a torch aloft to resemble a famous statue.
The Vikings see the signal and land their boat; believing the Gauls to be native to the island, they try to persuade them to board their ship, while the Gauls try to persuade the Vikings to let them board their ship - but the Language Barrier prevents them from realising they are trying to achieve the same thing (although Dogmatix and Huntingseassen are more successful at communicating with each other). As the real natives show up looking for the Gauls, they decide to make a run for the boat just as the Vikings decide to try forcing them aboard; in any event, they all end up on the boat together, leaving only the animal skin on which the pictures of their hunting trip had been painted for the natives to find. The distraught chief's daughter lays flowers at the foot of a totem pole depicting Obelix, Asterix, and Dogmatix.
The Viking ship returns to Denmark, where the explorers' tribal chief, Odiuscomparissen, is furious at Herendethelessen for wasting time and resources on an insane "voyage of discovery" instead of going on raids. Herendethelessen reports that he found the new world he swore existed, and offers the Gauls as proof. The Gauls, not sure where they are or why they have been brought there, try to ask for directions, but the language barrier gets in the way again and they are taken back to the Viking village where Haraldwilssen, the intellectual, gives an account of Herendethelessen's voyage. The impressed Odiuscomparissen decides to make the Gauls the guests of honour at the evening's feast before sacrificing them to the gods.
Fortunately, the Gauls are spared from being sacrificed when one of the slaves at the feast recognises them as fellow Gauls. Odiuscomparissen now believes Herendethelessen just skived off to Lutetia for a few months, and as the would-be explorer threatens to kill the Gaulish slave for lying and making him look foolish, Obelix leaps to his defence and a fight breaks out. The Gaulish slave, Catastrofix, ushers the three Armoricans out while the Vikings are distracted, explaining that he is a fisherman who was captured during a raid, and this is their chance to escape back to Gaul in his fishing boat (as it still contains his net, Asterix decides to ask him a favour on their way home). The Vikings finally notice the Gauls have fled, but Odiuscomparissen decides that they've had a good fight and a good laugh, and forgives Herendethelessen for telling tall tales. Herendethelessen is left wondering if he really did discover a new world.
Cacofonix spots the returning Asterix, Obelix, Dogmatix, and Catastrofix, and they are welcomed back by the other villagers, although Unhygienix is underwhelmed by the quality of the fish they caught in Catastrofix's net. Getafix is intrigued by Asterix and Obelix's stories of the strange island they found on their voyage, but such thoughts are soon forgotten as they sit down to the obligatory banquet... except for Unhygienix, who would rather sulk under a tree.
- Animal Talk: Although there does seem to be a difference between the "dog languages" of Dogmatix and Huntingseassen, they quickly overcome it. They thus realize the wrong assumptions their respective owners have about each other, and have a good laugh about it.
- Arranged Marriage: Obelix is horrified when Asterix points out that he is being lined up for one of these with the daughter of the tribal chief with whom they are staying, as the chief thinks Obelix's hunting prowess would make him a perfect son-in-law.
- A Birthday, Not a Break: Even on their captain's birthday, the pirates are not safe from the Gauls. At least the Gauls decide to spare their ship for once.
- Braids, Beads and Buckskins: Even Asterix was not above treating Native American tribes as completely interchangeable, and some of the natives the Gauls encounter seem to dress daily in the sort of elaborate costumes usually reserved for special occasions.
- The Chief's Daughter: Obelix is expected to marry her, causing him and Asterix to flee.
- Combat by Champion: The tribe's best warrior, who looks like a bodybuilder, plants his spear in front of Obélix, who slaps him away. Astérix, figuring "When in Rome", plants his sword in front of another Indian (who's built more like Obelix), who suffers the same result.
- Defeat Means Friendship: Asterix and Obelix are allowed to join the tribe after besting their best warriors.
- Every Episode Ending: Subverted; Cacofonix is present at the banquet, although Fulliautomatix is bashing him with his hammer to keep him from singing. Instead, Unhygienix is the one sitting under the tree, turning up his nose at a plate of fish being offered to him by his wife, Bacteria.
- The Food Poisoning Incident: Vitalstatistix' shield bearers suffer from food poisening off-panel due to eating rotten fish from Unhygienix.
- Foreign Queasine: When Asterix and Obelix are having their first meal with the local native tribe, they don't recognise the meat they are eating. Obelix looks at the man sitting next to him, points to his plate, and asks, "Gobble gobble?" The native replies, "Woof woof." A green-faced Obelix slowly puts the plate down again.
- Funny Background Event: While the villagers are seeing Asterix, Obelix, and Dogmatix off on their fishing trip, Fulliautomatix is hammering Cacofonix into the sand up to his waist to stop him singing a farewell ballad.
- Historical In-Joke: Much like Leif Erikson, the Viking who first discovered America in 1000, and Christopher Columbus nearly 500 years later, Asterix and Obelix have no idea that they've discovered a new continent. They describe it to Getafix as "a funny sort of island".
- Hypocritical Humor: In the comic, Obelix complains to Asterix about "this fat Hyberian girl" (the Chief's daughter) following him around. She may be on the plump side, but for Obelix to call anyone "fat" is really taking the cake.
- Injun Country: Asterix, Obelix and Getafix land in the Northeastern Woodlands. But the local Natives look more like Natives of the Plains than Northeastern Woodlands, somehow.
- Insane Troll Logic: The reason for the notoriously low quality of Unhygienix's fish is explained: he never fishes himself, he buys his wares from wholesalers who have certified it as high quality fish. The fact that the quality of the fish might drop when transported from Lutetia (Paris) to Armorica (Britanny, several hundred kilometers West from Paris) by oxcart over two weeks never occurs to him.
- Language Barrier: Much of the confusion between the Gauls, Native Americans and Danish arises because Gaulish is of a peripheral branch of the Indo-European language tree, Proto-Germanic is of a central branch, and Proto-East-Algonquian is no relation at all (and completely unfamiliar to the Gauls).
- Mistaken Nationality: Asterix and Obelix mistake the Native Americans for Cretans, then Iberians. Obelix mistakes them for Romans disguised as turkeys. The Vikings assume the two are Native Americans.
- No Indoor Voice: Viking tribal chieftain Odiuscomparissen always shouts his lines.
- No Name Given: Because the natives' communication with each other and with the Gauls is almost entirely non-verbal, none of them are given a name - not even significant characters such as the chief or his daughter.
- Painting the Medium: The Vikings' diålect øf Prøtø-Germånic is shøwn ås here. When Åsterix's høvercråft is full of eels, the diåcritics åre misplåced. Ålsø, å Gåulish slåve speåks with å heåvy åccent, shøwn with squåres øver the Å's ånd diågønal lines gøing the wrøng wåy in the Ø's.
- Reference Overdosed:
- Several references to the United States are made: roast turkey, the Air Force, the fifty stars, the Star Spangled Banner, the Statue of Liberty, Neil Armstrong, and of course, hot dogs.
- Several references to Denmark are made. The Vikings have a Great Dane as their pet dog. When they are "greeted" by Odiuscomparissen (if one can call the Ancient Viking equivalent of "Where the hell have you been!?" a greeting), one of them says, "Who would you expect? A mermaid?", in reference to the statue of the Little Mermaid in Copenhagen.
- The play Hamlet is referenced a few times as well, since it takes place in Denmark. The Viking leader Odiuscomparissen holds up a skull and ponders: "Something is rotten in the state of...", in reference to the skull held up by Hamlet in the play and the line "something is rotten in the state of Denmark". Also, when Herendethelessen wonders whether he really is the discoverer of foreign land, he says, "To be or not to be, that's the question?"
- In the English translation, Herendethelessen's followers include Steptoanssen Shifty Eyes (a reference to the 1960s and 1970s sitcom Steptoe and Son) and Haraldwilssen the intellectual (a reference to 1960s and 1970s UK Prime Minister Harold Wilson).
- Series Continuity Error: Unhygienix refuses to eat fresh fish directly from the sea, but in previous albums does exactly that and clearly enjoys it. There's no explanation for why this has changed.
- Telegraph Gag Stop: A Viking starts to describe his voyage as an emphatic saga, but when the chief yells at him to wrap it up he tells it this way.
- Throw the Dog a Bone:
- As it is mostly set in either America or Scandinavia, this is the only Asterix album from the Goscinny era in which not a single Roman is beaten up (though it happens aplenty in the animated adaptation). Only two panels even feature any Romans, as a Roman patrol listens to the latest fight over Unhygienix's fish from just outside the village, happily remarking how nice it is when the Gauls fight each other for a change.
- The pirates appear, but since it's the captain's birthday, the Gauls refrain from sinking them. They do steal the entire birthday feast (except for a sausage), however.
- Tipis and Totem Poles: Asterix and Obelix are implied to have landed near the modern day location of New York City (the fact that Asterix's signal to the Vikings pays homage to the Statue of Liberty indicates that he and Obelix landed on Liberty Island after fleeing the native village). So why the local indigenous people live in tipis (generally only used by Great Plains tribes) and build totem poles (an artistic medium specific to tribes of the Pacific Northwest) is anyone's guess. This would be like having ancient Dacians living in medieval castles and dining on cheeseburgers made with cuajada.
- Traveling Salesman: Discussed when the Vikings offer beads to the Gauls. Asterix assumes they're door-to-door salesmen trying to flog their stuff to them.
- Truth in Television: In ancient times, it was often thought that there were dragons in unexplored reaches of the Earth. And often cod fisherman are thought to have explored the waters of the Atlantic Coast decades before the Columbian Exchange.
- Vacation Episode: Asterix and Obelix unknowingly discover America and (very briefly) visit Denmark.
- Woolseyism: In the Icelandic translation of this album, rather than merely being an expy of him, Herendethelessen is Leif Eiriksson while Odiuscomparissen is his father, Eirik the Red. The other viking crew members are also given the names of notable Norse/Viking figures, including Thorfinn Karlsefni and Ari the Wise. The vikings are depicted speaking in flowery old Norse akin to the Icelandic sagas, making a handful of direct in-jokes. Their home is implied to be in Iceland rather than Denmark. While all of this might make the story more amusing to an Icelandic reader, it's also a raging anachronism even by Asterix standards given that none of the people in question were born for another millennium and Iceland wasn't even settled yet.
- These Natives are Crazy!