PlotIt is Valentine's Day and Popeye has forgotten to send Olive a Valentine, so she decides to assert her independence by taking the Valentine's Day Sweethearts Cruise. There, she is convinced, she will find her 'Mr. Right'. However, the Sea Hag has the same idea to take the cruise, also assured that she will find her 'Mr. Right' i.e. Popeye. Popeye goes to visit Olive and finds that she has left for the cruise, leaving him a 'Dear John' letter on her front door. This reminds him that he has forgotten Valentine's Day. Bluto arrives just after Popeye because he intended to ask Olive to be his Valentine. The two head for the cruise ship to join Olive.
Bluto manages to book a passage for the voyage and drives up in a big chauffeur-driven limousine wearing a white tuxedo to impress Olive. Bluto starts to put the moves on Olive even before they leave port. Popeye must talk Captain Wimpy into letting him onboard by offering to be part of the crew for free.
Once they set sail, Bluto and Olive are strolling along the decks in one of the cruise liner's Sweethearts Strollers. Olive is making Popeye jealous so he switches places with the deck hand pushing the stroller (Oscar) to get closer. After Olive and Bluto discover Popeye, Bluto ties him to an anchor and throws it overboard. Meanwhile, the ship is sailing into the Devil's Triangle, home of the dreaded Sea Hag, and Popeye is sinking straight to her.
She plans to keep him captive so she can find King Neptune to marry them. Popeye frees himself from the anchor, but the Sea Hag turns into an octopus to stop him. Popeye escapes by tickling her but she tells Popeye that he will be her Valentine.
When Popeye swims back to the cruise liner, Bluto is by the pool flexing for Olive and all the other ladies. Popeye confronts him so Bluto shows off by doing a high dive into the pool. When Popeye goes to perform his dive, Bluto trips him so he lands face down in the water.
Later, Captain Wimpy notices a beautiful young woman floating in the ocean and stops the vessel to help her. Popeye and Bluto both struggle to rescue her but Popeye reaches her first. As the woman shows her gratitude to Popeye for saving her, Olive gets jealous. After Popeye escorts the woman to her cabin, she begs Popeye to stay with her and become her prince. However, Popeye's heart belongs to Olive and he tells her so. After Popeye leaves, it is revealed that she is the Sea Hag in disguise.
The Sea Hag realizes that the key to winning Popeye is to get rid of Olive Oyl. The witch casts a sleeping-spell on Olive and the only way to break it is for Popeye to pledge his love to the Sea Hag - which he refuses to do. The Sea Hag then works out a deal with Bluto which would take Olive off her hands and make Popeye vow his love to her. Bluto agrees, and to make sure her plan works, the Hag gives him super-strength.
Popeye's spinach is more than a match for the strength spell so the sailor is able to outwit both villains. He knocks Bluto senseless then puts him in a Popeye costume. Popeye tricks the Sea Hag into removing the spell from Olive and marrying the disguised Bluto. Popeye is reunited with his one-and-only: Olive.