The movie starts with three dogs in a storm. The father sends his children to a lifeboat while he stays on his ship. In the morning, Salty the Seagull and Echo the Dolphin notice the pups and bring them aboard the deck. Echo goes looking for Captain Dogwood, the father of the pups. The pups introduce themselves as Andy and Tina. Salty agrees to help find their father because he knows him. The only way to get to him is with Little Toot, a tugboat who used to be the busiest and proudest until the boats no longer needed him and he sat in the docks feeling sorry for himself until he grew dirty and messy and became the home for three cats, who make anything miserable.
They plan to dispose of the cats by scaring them, since cats are scared of dogs. At first the cats are petrified, but once they realize they are just puppies, they feel much less intimidated. The pups want them off Toot, but they refuse saying they need him to collect a shipment sardines they heard Dogwood was delivering. They also threaten to throw the pups overboard and feed them to a shark, until Salty gives Toot the encouragement he needs to get shoo the cats away. Toot uses his hose on the cats since they also hate water. It works and the cats run away. The crew then start to clean Toot up until he is ship shape once again. Echo returns and tells them that Dogwood is shipwrecked on an island. Salty goes to collect his most favorite food, Percy's Perfect Purple Pickle Pelican Pellets, while the others collect bubble gum and ice cream. As Little Toot chugs off, the cat Claws leader vows to use him to find all the sardines.
As Salty boards Toot, the gang travels many miles and destinations until they meet Typhoon Tessie, the weather lady. She proclaims that she knows what happen to Dogwood, saying she was responsible for the storm because it is her job to create the weather. She warns them that she must have her job to make sure the weather changes. She soon starts her weather storm and the gang battles through the weather. Meanwhile, the cats try to reach Toot, but battling the weather makes it difficult for them. They call out to the crew, and Toot heads back to save them.
When Salty points that they are heading towards Skull Rocks, the cats beg to return to their boat, only for it to sink. Lucky, Echo calls out to Toot to surf. By the time they make it out safely, the stormed has calmed. The pups congratulate Toot, while Salty orders the cats to clean up Toot, much to their chagrin. They make it to the island and find Dogwood's ship partly wrecked but safe. While Salty and the pups head out to find Dogwood, Toot falls asleep and the cats use the rope to tie the captain's ship to Toot, because they think that there are sardines in the kitchen. They find Dogwood who wakes up, happy to see his kids and Salty. Suddenly the volcano starts to erupt and they board Toot and sail out, while the cats manage to tie the ship on to Toot and be towed away. Lava blocks their way, but Toot has an idea. They put all the bubblegum in his mouth and he starts to blow a humongous bubble. They fly over the lava just in time.
As they float back down, they all congratulate Little Toot promising that there is still lots more for him to do and he replies that he will never feel sorry for himself again. As for the cats, they search the ship to find the sardines, only for Dogwood to reveal that he threw them overboard to lighten the boat, much to their dismay. When Toot compromises that they might like the pickles, Salty throws a fit refusing to share the pickles because he loves them so much, then starts babbling controllably until he manages to laugh at his own expense. Everyone begins to have a good laugh, except for the cats who decide to eat whatever is left on the ship and depressed that they don't have any sardines. As the rest of the gang laughs, they all head back to the harbor.