Popeye wakes from a nightmare where he sees his long-lost father facing dire peril. Now determined to find his Pappy once and for all, he brings his ship to port where he is reunited with Olive Oyl, then, together with his adopted son Swee'Pea and Bluto (who is his first mate in this film), they all set sail again in search for Pappy. J. Wellington Wimpy stows away with designs on their food reserve. The journey takes them through the Sea of Mystery where the Sea Hag resides. The witch sees the sailor approach and becomes enamored with him, her schemes involving a disguise as a siren and turning Popeye and Bluto against each other.
Eventually, Popeye's dad is found on an island but rejects his son. The Lady of the Deep takes advantage of the situation and hypnotizes Popeye. Popeye and the Sea Hag try to kiss, but the sailor's family arrive to save him. In the last battle against the witch, Popeye eats his spinach and defeats the enemy.
- Billy West as main protagonist Popeye / Poopdeck Pappy
- Kathy Bates as the Sea Hag/ Lady of the Deep (the main antagonist)
- Garry Chalk as Bluto (the deuteragonist)
- Tabitha St. Germain as Olive Oyl / Swee'Pea
- Sanders Whiting as J. Wellington Wimpy (hamburger lover and the tritagonist)
- Frank Welker as the sea serpent (the secondary antagonist)
- Popeye's Voyage: The Quest for Pappy at the Internet Movie Database