Misty has returned to Cerulean City to step in as the Cerulean Gym Leader. But as soon as she arrives, she hears a news report about the Pokémon Investigation Agency closing Gyms that fail to meet proper standards—and rumor says Cerulean City is their next stop! Unaware that three of her enemies are in town, Misty rushes to the Gym and finds an out-of-control Gyarados in the pool. Neither Nurse Joy nor her sister's fan club can control it, and she can't just stick it in its Poké Ball while it's still upset. It's Misty's duty as Gym Leader to solve the problem, except she's also had a Gyarados phobia ever since she was a baby!
Misty puts on a water show costume and swims in the pool, hoping to stir Gyarados's memories of performing together back when it was a Magikarp. Instead, Gyarados turns the pool into a raging whirlpool, and Misty blacks out. As her Horsea rescues her, she dreams of Ash and Brock telling her she can do this on her own. When she comes to, however, she reluctantly puts Gyarados in an underwater cage, hoping to protect the other Pokémon. But all this time, her three foes—the Invincible Pokémon Brothers Kim, Kail, and Kai—have been spying on her, and this is their ticket to taking over the Gym!
Right then and there, Kim challenges her for leadership of the Gym and invites everyone in the city to watch. Misty has no choice but to accept, and she sends out Staryu. Kim's Hitmonchan pretends it can't swim, and when Staryu goes to rescue it, it knocks Staryu out with one hit! Nurse Joy, the referee, declares this an illegal trick and gives Staryu the victory. Next, Corsola faces Kim's Tentacruel, but the other two brothers send out their own Tentacruel and have them gang up on Corsola. Outraged, Nurse Joy disqualifies the brothers and bans them for cheating—but to force her to reverse her ruling, the brothers simply turn their Tentacruel on Gyarados!
Misty jumps into protect Gyarados, taking the brunt of the Tentacruel attacks. Gyarados breaks out of the cage and saves her, then blasts the brothers and their Tentacruel right out of the Gym. Nurse Joy reveals herself as a Pokémon Inspection Agent, and the Cerulean Gym has passed her test. Now that Nurse Joy is headed to Hoenn, Misty asks for a favor—if Nurse Joy sees a Trainer named Ash, tell him that Misty is a real Gym Leader now!
Following her travels with Ash and Brock, Misty is on her way back to Cerulean City to take over as the Gym Leader. As she arrives in town, she notices a lot of people congregating around a large television screen. On it, there is a news report about the Pokémon Inspection Agency, which has just closed down their fourth Gym in less than a month. It cuts to Agent Thedora, who explains that they are nailing down on anything substandard. Hearing rumors that they were on their way to the Cerulean Gym, Misty rushes to get there before they do since the Gym will certainly be shut down if there's no Leader present. Before she can get there, she is spotted by the Invincible Pokémon Brothers, who are determined to get revenge.
Finally at Cerulean Gym, Misty calls out to see if anybody is there. However, everyone is preoccupied by a Gyarados in the swimming pool that seems very angry. At the side of the pool is Nurse Joy with four boys, one of which falls in. As the Gyarados begins to chase him, Misty arrives and asks what's wrong. The boys introduce themselves as the local chapter of the Sensational Sisters’ fan club, and comment that Misty is almost as pretty as her older sisters. They explain that they were looking after the Gym until Misty got back, but Gyarados has been in an endless rage for days, and they can't calm it down. Nurse Joy explains that it is caught in an endless agitation loop, and suggests that Misty could think of something. Misty decides to try to get Gyarados to return, but Joy tells her that it won't work while Gyarados is so distressed. Next, Misty sends out Politoed. However, Psyduck also comes out, and falls into the water. Before it drowns, Gyarados headbutts it out, hitting the boy who is still in the pool, and sending them both onto the poolside. As Politoed claps, the fan club make a hasty exit while Gyarados continues to rage.
Misty and Joy head downstairs, where Misty is reunited with Horsea and Starmie. However, Gyarados is now in the aquarium and Misty needs to figure out what to do. Joy confirms that she will need to find a way to rein it back in. However there is a problem; Misty has a fear of Gyarados that goes back to when she was a baby. As she was crawling along, she crawled into the mouth of a Gyarados and was almost eaten. Misty decides that she will have to get over her fear if she wants to uphold her responsibility. Watching in the window, the Invincible Pokémon Brothers decide to use the Gyarados problem against her.
Misty in now on the diving board in her mermaid costume. She explains that she once took part in a water ballet with the Gyarados when it was a Magikarp, and that recreating their special moment may calm it down. After diving into the water, she is joined by the Gym Pokémon, who dance with her. Gyarados watches for a moment, but then uses Whirlpool on them. Trapped, Misty runs out of air, but in her last moments of consciousness she sees Horsea pushing her to the surface.
In a dream, Misty sees Ash and Brock, who congratulate her on finally becoming the Cerulean Gym Leader. Misty tells them that they made a mistake, and that she is not good enough. But they say that of course she is, and that they believe in her. As they float away, Misty calls out for help, but they don’t return. Suddenly, her foot becomes trapped by Gyarados's tail. She scream in response, waking herself up. Nurse Joy offers her a hot tea to settle her nerves. Nurse Joy suggests separating Gyarados for the safety of the other Pokémon, and Misty agrees. Misty gives Gyarados one more chance to return its Poké Ball, which is resisted. She traps it in a cage, which Gyarados can't get out of, leaving Misty feeling bad for it.
Before she can contemplate too much, the Invincible Pokémon Brothers, Kim, Kail and Kai, challenge Misty to a battle for a change of the Cerulean Gym Leadership over the loudspeaker. The residents of Cerulean City rush into the spectator stands to watch the battle unfold. The brothers tell Misty that allowing a Pokémon to control her makes her unfit to lead a Gym, which Misty denies is true, but Kim states that there should be such a rule and suggests that she is too scared to battle because she would lose easily in front of everyone. Kai gets the crowd to encourage Misty to battle, as a result, she decides to accept the challenge. Nurse Joy announces that the battle will consist of three one-on-one matches, best 2 out of 3. Misty sends out Staryu, while Kim sends out Hitmonchan. Hitmonchan begins to drown, so Misty tells Staryu to help it out. However, it was a decoy and Hitmonchan punches Staryu, who goes down in one hit. Misty calls out Kim for his dirty trick, but Kim states that he's playing to win, however, Nurse Joy declares Hitmonchan's move illegal and proclaims Staryu the winner, much to Kim's shock.
Next, Misty sends out Corsola, while Kim sends out Tentacruel. Tentacruel starts out with Bubble Beam, which hurts Corsola badly. However, Misty orders a Recover, and then sends Corsola into a Tackle attack. As Corsola heads towards Tentacruel, Kail and Kai send out their own Tentacruel, which both bash into Corsola. As Corsola crashes into a rock near Gyarados, Nurse Joy tells them that it is a rule violation. However, Kim denies this, stating that the challenge was from the Invincible Pokémon Brothers as a group, not just one single brother, disregarding the fact that the challenge is supposed to be a one-on-one battle. Misty comments that Kim is too chicken to fight by himself and the brothers respond by ordering the Tentacruel to use Poison Sting. Corsola is badly hurt, and so Misty dives in to save it.
Kim declares that the "chicken" has tied the match 1-1, but Nurse Joy states the opposite and disqualifies them for their continued rule violations. The Invincible Pokémon Brothers are angry at being denied of their "fair and square" win, but their tantrum only makes Nurse Joy ban them from all official Pokémon matches. In an attempt to force Nurse Joy to reverse her ruling, the Invincible Pokémon Brothers order their Tentacruel to use Poison Sting on Gyarados. Nurse Joy tells the Invincible Pokémon Brothers to stop, but they demand to have their ban lifted and be given the win. Misty impulsively dives in front of the stings and takes the hits herself to protect Gyarados. Gyarados is taken aback by how far Misty is willing to go to protect it. Kim's Tentacruel tackles her into the cage, and the air is knocked out of her. As Misty floats down to the bottom of the pool, the Invincible Pokémon Brothers watch and sadistically take enjoyment in her suffering. Gyarados becomes horrified that Misty could drown, and it frantically begins to bash the cage again. As everyone other than the Invincible Pokémon Brothers watch in worry, Gyarados smashes open the cage. Gyarados quickly lifts Misty to the surface.
The Invincible Pokémon Brothers are not happy with this turn of events, and order their Tentacruel to attack with Bind, Bubble Beam, and Hydro Pump. However, Gyarados easily deflects their attacks before using a Hyper Beam to send the Tentacruel blasting off. After seeing Gyarados glaring at them, the Invincible Pokémon Brothers cowardly call quits, only for a Hydro Pump to blast them and Hitmonchan off once and for all. As the crowd cheers, Gyarados happily agrees to return to its Poké Ball. Nurse Joy congratulates Misty on proving herself as Gym Leader and that her Gym has passed inspection. Misty is confused, but Joy explains that she is a Pokémon Inspection Agent.
Outside the Gym, Agent Joy explains that she is now going to the Hoenn region. Misty asks her that if she meets Ash, to pass along a message that Misty has finally made it as a Gym Leader. Agent Joy agrees and then sets off. As Misty watches her go, she thinks of Ash and Brock and knows that they were right that she could do it on her own. As a new chapter of Misty's life begins, she begins training the Gym Pokémon, as the journey continues.