On a ship sea, at night, the captain and sailor see giant tentacles smashing their ship into pieces. The captain then sees a giant head with tentacles coming out of its "neck." At the palace, the captain tells everyone what happened. The Sultan suggests that they should have a crew to retrieve the cargo and Aladdin suggests that it should be himself. But the captain suggests that they should have Captain Al Bahtross, a nautical hero who defeated the Seven Fleets of Jambalaya. Jasmine and Sultan agree with Aladdin being jealous and deciding to go with the captain to see who's the great hero.
When Aladdin, Abu, and Iago get down at the docks, Aladdin sees how great of a hero Al Bahtross is. Aladdin makes Genie come out to make him be dressed in a fancy pirate outfit. When Aladdin gets to the ship, he tells the captain that the Sultan orders him to go to a salvage precious lost cargo. Al Bahtross makes Aladdin his crew and they head off. On a stormy night, Aladdin tells Al Bahtross that they should go below deck, but the captain wants to stay under the storm. So Aladdin ties himself on a ship mast.
The next morning, Abu shows everyone the figurehead of the lost ship. Al Bahtross says that they're in Neptune's Triangle, the deadliest waters known to man. The captain makes everyone dive in the water, but Genie, Iago, and Abu want to stay on the ship. So only Aladdin and Al Bahtross get in the water. They go to a shipwreck to tie a rope on a treasure chest. Aladdin tugs the rope and Genie lifts the treasure to the ship. Aladdin and Al Bahtross see the giant head from the other captain's story and they get caught inside while the others are on the ship worrying about the two. Aladdin and Al Bahtross find themselves in a control room and find Mechanicles, who was controlling the head. Al Bahtross is about to fight him, but the villain cages the captain and Aladdin. Mechanicles tells the two his plan on boiling the ocean steam cleaning the Earth. Al Bahtross bends the cage bars and he and Aladdin climb out, but Mechanicles pulls a lever that opens a trapdoor beneath them. Mechanicles tells them that they're in salt filter and the chamber will be filled with salt and they'll suffocate.
Meanwhile, Genie, Abu, and Iago are in the ocean looking for Aladdin and Al Bahtross. They then see Mechanicles's machine and they get sucked into it. They all land in the salt filter where Aladdin and Al Bahtross are, which is getting filled with salt. Genie pulls out a plug he's standing on and everyone gets sucked back into the ocean. They all get back on the ship and Al Bahtross wants to ram the machine and Aladdin tries to stop him because he'll end up wrecking the ship. The two then fight over the wheel until they accidentally roll overboard, pulling Abu with them. When the three get back up, they see the machine's tentacles destroying the ship. Aladdin makes Genie grab the treasure chest two that they can use it to plug a hole.
Mechanicles pulls a lever which makes the tentacles grab Abu and Al Bahtross. Aladdin is about to free Al Bahtross but the captain tells him to stop the machine. Genie is in the water with the treasure chest. He gets sucked in the machine, but the treasure gets lodged in the hole, shutting down the machine. Aladdin gets in the machine's control room and chases Mechanicles. When Aladdin stops at the control panel, Mechanicles tells him not to push it because it'll destroy the machine. Aladdin pushes it and the machine gets destroyed.
Aladdin and the others get on a large piece of driftwood with the treasure chest. Al Bahtross thinks that he destroyed the machine and Aladdin reluctantly accepts the captain being the great hero. Everyone is now going back to Agrabah.