The kids are relaxing at the Grand Wazoo Resort on Wazoo Island when a man emerges from the water completely covered in seaweed. His name is Adam, and he is a treasure hunter who believes he has just uncovered the location of the King Neptune, a cargo ship that was wrecked long ago.
Adam and the kids go searching for the wreck in a sub, secretly followed by Team Rocket in their Magikarp sub. Team Rocket fires a missile at them and zips ahead. Adam and the kids manage to find their way to the cavern where the ship is located, where lots of Relicanth have made their home. Adam finds a trunk. Team Rocket shows up again to take the trunk, also destroying the ship.
Team Rocket then destroys the exit to the cave as they leave, and heads to the surface. Adam's sub follows the Relicanth out and catches up with Team Rocket. Angry at the destruction of their home, the Relicanth use Hydro Pump on Team Rocket, while Pikachu finishes them off with Thunder.
Opening the trunk, Adam discovers that the King Neptune was only carrying lots of Green Shards. Aside from that, he does have one real treasure to show for this adventure—the friendship of the Relicanth.
While still on their way to Mossdeep City, Ash and his friends have stopped off at the Grand Wazoo Resort's famous beach. There, they notice a shape in the water, and a weird, laughing seaweed creature emerges, scaring the group. Ash wonders if it is a Pokémon, but the creature is soon revealed to be a treasure hunter named Adam. He produces a necklace from his loot bag, which he claims is made of rare emeralds. He explains that he dives in search of treasure for a living, and takes the group back to his shop, where many deep sea treasures are for sale. Adam's wife Evelyn examines the necklace, but reveals that the necklace is made of Green Shards, which are somewhat valuable. Adam is disappointed, but explains that he really hopes to find the long-lost treasure from a sunken cargo ship called the King Neptune. The century old mystery has intrigued treasure hunters like himself. Adam goes on to say that he believes there is a connection between the local Relicanth and the treasure, because he found that necklace hooked onto a Relicanth. Ash then looks up Relicanth in the Pokédex, and the group speculates for a bit. Adam expresses his determination to find the Relicanth again and hopes they will lead him to the treasure, and Ash says they would love to go with him. Team Rocket overhears the entire conversation, with Jessie and James thrilled by the thought of sunken treasure. Meowth reminds them that the treasures would be a welcome gift for the Boss, and way to get their promotions. They cheer at the thought and become determined to get the treasure.
Out on the ocean, Evelyn mans their boat while the others prepare to dive down in Adam's submarine. After preliminary checks, it is full speed ahead, and the diving mission is on. As the sub dives into the darker, deeper parts of the ocean, Adam turns on its headlights, illuminating some intriguing deep sea Water Pokémon. Finally, a Relicanth appears on Adam's monitor and radar. Just then, the ship shakes violently, and Evelyn radios down to check on them. Another monitor shows the cause of the disturbance—a giant Magikarp that is ramming the sub. Ash recognizes it as Team Rocket's Magikarp Submarine and warns Adam about them, while Evelyn listens worriedly from above. Inside Team Rocket's sub, they paddle along doggedly, and James sends out Chimecho to give them added motivation. Meowth hits a button and successfully fires two torpedoes which damage Adam's sub. Team Rocket pulls up alongside them and taunts via radio that they will get the treasure first. Everyone is okay, so Adam radios their situation to Evelyn and says they are going after Team Rocket and continuing their mission. Ahead, Team Rocket are following a Relicanth they think might lead them to the treasure, and Jessie orders them to push forward despite their sub beginning to flood. Team Rocket soon loses control and is helpless as their sub is pushed along by a current. Adam and the others have caught up now and again have the Relicanth in their sights. Despite the deep sea turbulence, Adam suspects that they must be close and follows the Relicanth into a small tunnel. Above, Evelyn worriedly tries to raise them on the radio, but communication is now knocked out due to their location. Adam skillfully maneuvers the sub through the small tunnel, but the rough current causes him to eventually lose control, so everyone hangs on and braces themselves.
Later, the group awaken unharmed. All the sub's interior emergency red lights are on now. They look out the window and discover they have made it to shore in an underwater cave containing an old sailing ship, which Adam declares must be the King Neptune. Adam rushes off to explore the ship while the others discuss their situation. Presently, a group of Relicanth emerge from the hull of the ship, and the group admires them. Adam suddenly emerges, having found a treasure chest.
Just as he is about to open it, a voice from the water interrupts; it is the radio from Team Rocket's Magikarp sub, and they emerge and say their motto. Meowth hits a button and shoots out a rope-tied plunger to snatch the chest. As Adam rushes forward in anger, Meowth stops him by hitting another button that sends out two more torpedoes. Adam and the others duck as the torpedoes fly over them and strike the wrecked pirate ship, disturbing and endangering the Relicanth. Team Rocket gloats over their success, but notice that they are now surrounded by a bunch of angry Relicanth. Team Rocket yells at them, but to no avail. Jessie snatches the remote from Meowth and sends out two more torpedoes towards the Relicanth. Ash quickly sends out Corphish, who destroys the torpedoes with Bubble Beam. Team Rocket takes the opportunity to make their escape, and they even make sure they cannot be followed. Meowth hits another button that sends two rockets out from the back of their sub, causing a cave-in at the cavern exit. Adam, Ash, and the others are worried, but then they notice the Relicanth are all starting to swim in one direction. One of them pauses to call out to the humans, who realize the Relicanth must know of another way out. They get back in the sub and follow the Relicanth to another underwater tunnel, but the current looks rough in this one too. Adam assures them that they will make it through. After an anxious hour, Evelyn soon hears the speaker crackle to life and Adam informs her that they are returning to the surface. Back aboard the boat, Ash and his friends thank the Relicanth, while Evelyn scolds Adam briefly. But she has picked up Team Rocket on their radar, so they can still try to reclaim the treasure.
Some distance away, Team Rocket has also surfaced, and gloat over their victory, but that is when Ash and his friends catch up with them, accompanied by the group of Relicanth. From the boat, May sends out Bulbasaur to grab the treasure chest with its vines. Team Rocket won't let it get away that easily, and they grab the chest as well. Jessie sends out Seviper, who lashes Bulbasaur with Poison Tail, breaking its hold on the chest and sending it flying. Brock sends out Mudkip, who attacks Team Rocket with Water Gun as the Relicanth join in with Hydro Pump. Bulbasaur grabs the chest again with its vines and hands it to Adam. Finally, a Thunder from Ash's Pikachu sends Team Rocket blasting off.
Adam can finally open the treasure chest. Inside, everyone is surprised to only find more Green Shards. Adam is disappointed, but Evelyn says she can make some great jewelry out of them, much to May's delight. Evelyn even offers to make something out of them for May, who happily thanks her. Adam thanks the Relicanth for everything, and expresses determination to continue his treasure-hunting adventures. As the sun sets, Ash and his friends continue towards Mossdeep City.