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!
After the events of Gotta Catch Ya Later!, Misty is on her way back to Cerulean City. Misty comments to Togepi that they are almost home, and promises to get something to eat as soon as they get there. As Togepi happily cries out, Misty reaches the top of a hill and sees Cerulean City spread out before her.
As she arrives in town, she notices a lot of people congregating around a large TV 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. This means that any "unsafe, unclean, or uncool" Gym will be shut down by them. Hearing rumors that they were on their way to Cerulean City, 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 her sisters' fan club, and comment that she is almost as pretty as they are. 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, but 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 then 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 foggy area, Misty sees Ash and Brock. They ask what she is doing there and if it is true that they made her the Gym Leader of Cerulean. 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 that she needs their help. Suddenly, her foot becomes trapped, which is revealed to be held by Gyarados. She wakes up, and drinks the tea that Joy hands to her. 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 then traps it in a cage, which Gyarados can't get out of. Misty feels bad for it, but before she can contemplate too much the Invincible Pokémon Brothers make an announcement to Cerulean City. They announce that as Misty has lost control of her Pokémon (not exactly true since she never had control of it to begin with), it is time for a change of Gym Leader. They challenge Misty to a battle, with the winner becoming the new Gym Leader. The residents of Cerulean City rush in to watch the battle.
The Invincible Pokémon Brothers introduce themselves as Kim, Khan, and Kam. They tell Misty that allowing a Pokémon to control her makes her unfit to lead a Gym, and suggest that she is too scared to battle because she would lose easily in front of everyone. Misty accepts the challenge. As the boy who fell in the pool earlier begins the commentary, Nurse Joy announces that the battle will consist of three one-on-one matches. 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. Nurse Joy declares that to be an illegal move, and proclaims Staryu the winner.
Next, Misty sends out Corsola, while Kim sends out Tentacruel. Tentacruel starts out with BubbleBeam, which hurts Corsola badly. However, Misty orders a Recover, and then sends Corsola into a Tackle attack. As Corsola heads towards Tentacruel, Kain and Kon 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. Kim denies this stating that the challenge was from the Invincible Pokémon Brothers, and not just him. Everyone seems to forget that the challenge was for one-on-one battles. Misty comments that Kim is too chicken to fight by himself, and the brothers react by ordering the Tentacruel to use Poison Sting. Corsola is badly hurt, and so Misty dives in to save it.
Nurse Joy disqualifies them, and bans them from all official Pokémon matches. To try to reverse this, the Tentacruel are ordered to use Poison Sting on Gyarados. Misty impulsively protects Gyarados by diving in front of the stings and takes the hits herself. Gyarados is taken aback by how far Misty is willing to go to protect it. Kim's Tentacruel then Tackles her into the cage, and the air is knocked out of her. As she floats down to the bottom of the pool, Gyarados is horrified that she could drown, and it frantically begins to bang on the cage again. As everyone other than the Invincible Pokémon Brothers watch in worry, Gyarados makes a particularly powerful hit, making the cage collapse. Gyarados quickly speeds Misty to the surface.
The Invincible Pokémon Brothers are not happy with this turn of events, and order the Tentacruel to attack with Bind, BubbleBeam, and Hydro Pump. However, Gyarados easily reflects these, before using a Hyper Beam to send the Tentacruel blasting off. A Hydro Pump quickly sends the Invincible Pokémon Brothers to the same fate. As the crowd cheers, Gyarados happily returns to its Poké Ball. Nurse Joy congratulates Misty and tells her that she has proven herself to resume Gym Leader duties, 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.