In Vermilion City, the Pokémon Fan Club Chairman learns that Red is missing, and hastily tells Yellow of the legend of the Legendary Stones of Vermilion Harbor: "Some people think that down there in the ocean by Vermilion Harbor there are four Evolution stones that never disappear when used to make a Pokémon evolve: the Legendary Fire Stone, the Legendary Water Stone, the Legendary Thunderstone, and the Legendary Leaf Stone. Now, people had laughed at that legend... until Red's adventure brought him to Vermilion City. His Poliwhirl was thrown into the ocean, but evolved quite suddenly into a Poliwrath! And Poliwhirl only evolve with the Water Stone.
Yellow wants to go find the Legendary Stones, much to the annoyance of the Pokémon Fan Club Chairman — "They're supposed to be in a heavily guarded sanctuary! You can't just waltz in there!" But Yellow starts his search for the Legendary Stones anyway. On the ocean surface, Yellow floats on a large mass of Kitty's thread, with Omny in the Poké Ball on Yellow's fishing rod, trying to find a Pokémon that can dive down into the wide ocean. But all there are Tentacool! Suddenly, there's a tug on the line... from a giant Tentacruel! It pulls Yellow and his Pokémon down under the ocean.
Still holding his breath, Yellow sees a baby Tentacool with a tentacle stuck under a boulder! Yellow hastily sends out Gravvy and it lifts the boulder. But right then, Yellow has to open his mouth, and faints. He awakens still underwater, but able to breathe! He wonders if he is dead, but then sees the baby Tentacool and the Tentacruel and is happy for them. But that's not the most of this adventure — there are the Legendary Stones of Vermilion Harbor! The Legendary Stone of Vermilion Harbor. Only the Leaf Stone is there! It looks like the three other Stones... were taken!
When Yellow has returned to Vermilion City, he tells the Pokémon Fan Club Chairman the bad news, instantly sealing the Chairman into a pout. Yellow, meanwhile, wonders who took them, thinking that they must have had Fire, Electric, and Water Pokémon they wanted to evolve, because there is no one Pokémon who could evolve with all of those Stones. But then Yellow remembers Eevee, a Pokémon who can evolve with any of those three Stones, and that Red had an Eevee, so Yellow can't help but wonder if Red stole those Legendary Stones.