King Blozo has fallen into deep financial troubles. His kingdom's currency, the "Pezozee", has devalued substantially, and he comes to Castor Oyl and Popeye for help. He wishes to find Woo Fong to obtain a Chinese black parrot, which he sees as "a key to an enormous amount of treasure". As Popeye starts looking, Castor assigns a mysterious detective, master of disguise Merlock Jones, to escort him. During the search, a few other sailors have caught wind of this. They attempt to sneak up to murder him, to no result whatsoever.
Popeye successfully secures the parrot, named Oolong, as well as Woo Fong's ship, and immediately sails off to find the treasure (along with Castor, King Blozo, Oscar and crew). Olive Oyl initially fails to board the ship, and, after parachuting on board and getting a chaperoni by accident, she causes the crew of sailors to panic due to fear of bad luck. A violent brawl ensues, but Popeye manages to incapacitate the others.
Oolong reveals that the treasure they are hunting for is in the middle of the Eighth Sea, and that the course is tattooed on its chest. Merlock Jones starts playing his disguise tricks by turning into duplicates of Popeye, Oscar and even the ship's chef.
Things start to shake up, as strange people show up on board at midnight. It turns out that a few pirates have stowed away on the ship, going for the same treasure. The leader of them is Bluto, who finds Oolong and the treasure map, and plans to kill Popeye at dawn. When the time comes, both men engage in a notedly epic fight, and the scene devolves into a scribbled mess. They keep fighting for hours, and, despite their clothes being ripped apart, they never desire to take a rest. Eventually, Popeye unleashes his "Twisker Sock" and beats Bluto unconscious. The pirates are sent away on a lifeboat, and King Blozo gives Bluto a Pezozee as an insult reward.
The ship reaches the Land of Dooma, "a city of gold in an unknown sea", and the first person they encounter there is John Smith, a college professor/adventure book author who has been stranded in this place due to losing a pencil. He tells Popeye and friends that the natives use gold as building materials, thus, if they ignore how gold is valued in Popeye's world, the visitors could take as much as they wanted. Smith helps Popeye contact King Yoko, ruler of this land, and the visitors learn that his once-powerful kingdom is slowly sinking into the ocean, so the residents have mostly moved away.
After Popeye secures the huge stash of gold and they leave Dooma behind, the land finally crumbles into the ocean. John Smith intends to end his life immediately, but is saved by Popeye and brought onto the ship. The floor of the ocean starts to cave in, which causes giant waves to rise, putting everyone in danger. A series of disasters follow suit, and the ship is completely wrecked.
Despite the difficulties, Popeye and his friends, as well as John Smith, manage to safely reach dry land - Blozo's nation, specifically - without losing their $50 billion worth of gold. King Blozo has eliminated his "worries", leading to the next storyline, "Long Live the King".