After countless defeats at the hands of Popeye, the evil Sea Hag has devised a foolproof plan for revenge. She turns all of Popeye's friends into stone by removing their hearts and scattering the pieces across corresponding islands. Now Popeye must search for the hearts within each of the five islands in order to revive them. Not an easy task, as General Bunzo and his troops have issued a "100,000,000G" bounty for the hearts's retrieval. This prompts the likes of Bolo, Ox and others to try and collect them for the reward. Reading the issue as well, Brutus decides to also quest for the hearts in a plan to impress Olive, thus making this a race against time for Popeye to save his friends and put a stop to the Sea Hag's plan.
As Popeye, players will have to fight their way through different villains such as Bolo, Ox, Emok, General Bunzo and his troops, Bernard the Buzzard, the boss for most levels, Brutus, and the final boss, Sea Hag.
There is a two-player option where the second one controls a white-dressed Popeye (reminiscent of his Navy sailor incarnation from the older cartoons), both players making their moves through a split screen display.
The game's stages are large level maps that appear in the form of a board game, in which the player will have to take turns moving around, exploring each of its spaces, and obtaining the hearts of Popeye's frozen friends. There are also spaces that serve different purposes throughout the game. The beginning of each stage starts by showing the player which character has to be saved. Their heart then rises skyward and splits into various pieces, those pieces then scatter onto random spaces of the map, the space appearing with an enclosed heart. When on the map, the player presses the action button and wheel will appear with spaces numbered 1-6, which will help determine the player's moves during this phase of the game.
The various areas on each map are referred to as "courses". Upon entering them, courses appear in the form of side-scrolling platforming levels which players will have to complete in the allotted time. Players must explore various courses in order to obtain all the hearts. In some cases, exploration of a course may also reveal hidden pathways and shortcuts.
For the most part, Popeye's primary weapon is a large anchor-and-chain which he carries on his shoulder and uses like a bolo whip. Popeye can obtain power-ups for support, such as a tire to bowl over enemies, a propeller anchor for reaching high platforms, and a "KeroKero" (meaning "ribbit ribbit") which allows the player to become a frog for better maneuverability in water courses a la the frog suit from the classic Super Mario Bros 3. There are also items that inflict damage to enemies on the map such as a bomb ("Bakudan") and lighting anchor ("BuriBuri"). When a boss battle is about to be won, Popeye receives a can of spinach that gives the player invincibility and the ability to use their fists to deal the finishing blow.
The game's stages are:
- Stage 1: Popeye's home (J. Wellington Wimpy is saved here)
- Stage 2: Spinachovia (King Blozo is saved here)
- Stage 3: Goon/Jeep Islands (Eugene the Jeep and Alice the Goon are saved here)
- Stage 4: Ghost Rock (Swee'Pea is saved here)
- Stage 5: Sea Hag's Hide-Out Number 412 (Olive Oyl is saved here)