Mewsette is in love with the accomplished but shy mouser Jaune Tom but the former is frustrated with his plebeian ways (and those of the farm), to the point of calling him a "clumsy country clod".
Inspired by the human Jeanette's stories of the glamour and sophistication of Paris she runs away by taking a train to the big city, where she encounters the slick con-cat Meowrice.Taking advantage of the country kitty's naivete, he puts her in the care of the sultry Madame Henretta Reubens-Chatte, who promises to turn Mewsette into a dainty debutante known as "The Belle of all Paris". Unbeknownst to Mewsette, Meowrice is grooming her to be the mail-order bride of a rich American cat in Pittsburgh known as "Mr. Henry Phtt".
Meanwhile, Jaune Tom and his sidekick Robespierre arrive in Paris, searching for Mewsette. Training does not go well. Just as Mewsette is about to give up and return to the farm, Meowrice takes her out to see the cat side of Paris, the Eiffel Tower, the Champs-Élysées and the Mewlon Rouge. Reinvigorated, she returns to her studies. Jaune Tom and Robespierre arrive just at that moment but are waylaid by one of Meowrice's shadowy cat henchmen and barely escape drowning in Paris's famous labyrinthine sewers. By coincidence, Jaune Tom displays his incredible mouse-hunting skills in front of Meowrice (known as "Virtue-Mousety"), who sees a money-making opportunity, gets them drunk, and sells them as mousers to a ship bound for Alaska. On the ship, Robespierre consoles a depressed Jaune Tom, telling him that any problem, regardless of size, can be broken up into manageable pieces, by remarking that even the mighty ocean is made up of little drops of water. Jaune Tom has a vision of Mewsette singing about how no problem is unconquerable, and the importance of never giving up.
Mewsette finishes her training and is now lovely enough to impress even Meowrice, who commissions a series of paintings of her by such famous artists as Claude Monet, Henri de Toulouse-Lautrec, Georges Seurat, Henri Rousseau, Amedeo Modigliani, Vincent van Gogh, Edgar Degas, Auguste Renoir, Paul Cézanne, Paul Gauguin and Pablo Picasso (an opportunity for the animators to indulge in some artistic parodies), so that he can send them to Mr. Phtt. Meowrice quietly writes a check to pay his "sister", Mme. Reubens-Chatte (using disappearing ink, so that the check is worthless), and takes Mewsette to Notre Dame. There, he reveals his plan to ship her to America and tries to coerce her to enter a luggage crate, but after describing Mr. Phtt as fat and old, she manages to escape him and his sidekicks. In the resulting chase scene, she leads Meowrice and his henchmen onto a bulldog, who injures him badly enough to put him out of action for six weeks. Meanwhile, his sycophants (who are nowhere near as intelligent as he is) comb the city without success, searching for Mewsette. Meanwhile, not long after they reach Alaska (a howling wilderness of snow), Jaune Tom and Robespierre strike gold. Now wealthy, the two cats hurry back to Paris.
A disillusioned and homeless Mewsette wanders around the streets of Paris, eventually ending up sitting atop a bridge over the river, considering ending her misery ("Paris is a Lonely Town"), but Meowrice and his goons capture her. She is taken to the Gare du Nord railway station, en route to a boat to America, and all hope seems lost, when Jaune Tom and Robespierre arrive. They have been aided by Mme. Ruebens-Chatte, who is irritated that her own "brother" double-crossed her and tears up the worthless check. In a humorously over-the-top fight scene inside the boxcar of a moving train, the three heroes defeat Meowrice and pack him into the crate intended for Mewsette, doubtless that this will be a nasty surprise for Mr. Phtt. The film concludes with Mewsette, Jaune Tom and Robespierre enjoying the high life in Paris that Mewsette was seeking when she left home.