The goal is to complete different levels under the roles of film protagonists Nemo, Marlin or Dory. It includes cutscenes from the movie, and each clip is based on a level, e.g. hopping through a batch of jellyfish.
The story begins with Nemo, excited of his first day of school, waking up his father Marlin. While traveling to school, they come across Tad and Sheldon, who are also on their way to school but are unable to find Pearl, who is lost in the sea caves. Nemo wants to help but Marlin forbids it. They come across a large clam blocking their path. While Marlin suggests going home, Nemo enters the caves and finds Pearl. After helping her out of the caves, she gives Nemo a pearl as a reward. Nemo puts it inside the clam, causing it to close and clearing the path. They soon come across a pile of rocks blocking the path and Nemo darts to break through them. Nemo's new friends challenge him to a race. Afterwards, they encounter some fish-eating clams. After Nemo defeats them, they finally make it to school.
His teacher, Mr. Ray, arrives and after getting to know Nemo, they depart on a field trip to the drop-off. Along the way, Nemo plays with his new friends on bouncy sponges and exploring some caves. This causes them to fall behind. After catching up to Mr. Ray, he lets them explore freely. They spot a speedboat in the distance and Nemo decides to swim up to it just as Marlin catches up. After avoiding dangerous sea creatures, he succeeds but is chased by a diver. Another diver blocks off Marlin while Nemo is captured and taken on-board the speedboat, which then departs.
Marlin chases after the speedboat, but soon loses it. After noticing one of the diver's masks fall in the water, he chases it down. He makes his way through many caves filled with dangerous fish, before spotting some fish and tries to ask for directions but is ignored. He meets Dory, a blue tang who suffers from "short-term memory loss." She helps lead Marlin after the boat but after following her three times, she completely forgets what they were doing. Believing Dory is no help, he comes across a shark named Bruce, who is fish-friendly.
Bruce invites them to a party, while Marlin is skeptical, Dory accepts. While traveling through octopus-infested caves and minefields, they come across some mines that Dory decides to bounce on, in which Bruce warns her that over three bounces will make them explode. They reach sunken submarine where they meet Anchor and Chum. While having the meeting, Marlin finds the mask the he tried to catch earlier but an argument with Dory gives her a nosebleed. Bruce becomes violent after smelling the blood and tries to eat Marlin and Dory, forcing them to flee. After being chased around the submarine and temporally escaping into nearby rooms, they manage to escape Bruce and get out of the submarine.
Meanwhile, Nemo is placed in a fish tank in a dentist's office. After finding all of the fish hiding around the tank, he quickly befriends them. Back in the ocean, Marlin and Dory accidentally drop the mask into a dark abyss, and they follow it down. After making their way through a system of pipes, they suddenly encounter an angler-fish, who tries to eat them. They find the mask and Marlin distracts the angler-fish while Dory reads the address, pointing them to Sydney, before using it to trap the angler-fish to a rock and escape. At night, Jacques, one of the tank gang members, leads Nemo to the tank's volcano where must face a challenge to join the gang but needs to first fix some leaks before facing the challenge.
While continuing to Sydney, Marlin and Dory encounter a school of jellyfish. Luckily, the tops of the jellyfish don't sting, so they have a race to get out of the swarm. Marlin manages to get out but is forced to go back in rescue Dory from a jellyfish before escaping and passing out. Back in the tank, Nemo does some training with Gil, the tank gang's leader, and follows him around the tank. Back in the sea, after Marlin plays tag with Dory and hide and seek with some baby turtles, they have a race to reach their destination. In the tank, Gil has Nemo search for five pebbles needed to jam the filter as part of their means to escape. Meanwhile, Marlin and Dory accidentally get swallowed by a whale. They travel through the whale's body and eventually manage to find a way out.
Upon arriving in Sydney, the two fish meet Nigel who agrees to take them to the dentist's office. While they are en route, the dentist puts Nemo in a bag to give to his niece, but Nemo gets the idea to pretend to be dead so that the dentist will flush him down the toilet, which will take Nemo to the ocean. Marlin, Dory, and Nigel arrive at the office and are horrified to see Nemo "dead" before Nigal is thrown out. Gill saves Nemo from getting thrown in the trash can instead of the toilet and helps Nemo escape via the dentist's sink.
Nemo travels his way through the sewers and manages to find an exit. After finding Dory, they quickly search for Marlin, who is thrilled to see his son alive. Shortly after, a fishing net catches Dory and several other fish and tries to pull them out of the water. Nemo comes up with an idea to get all the fish to swim down. This successfully breaks the net and frees them.
After their adventure, Marlin is now not nearly overprotective of his son knowing he can look after himself. Dory also spends a lot of time with the two, and she accompanies Marlin as he takes Nemo to school.