Lou (voice of TOBEY MAGUIRE) is a young beagle puppy who yearns for something exciting in his life beyond just being someone's pet. He gets that chance when he's adopted by Carolyn Brody (ELIZABETH PERKINS), a suburban mom who's looking for a pooch to replace the family's missing dog that left's her son, Scott (ALEXANDER POLLOCK), in a deep funk.
It turns out, however, that the Brody's dog hasn't run off, but instead was kidnapped by a bunch of cats working for the nefarious Mr. Tinkles (voice of SEAN HAYES), a Persian cat who's scheming to take over the world from the mansion of his elderly and ailing human master, Mr. Mason. It seems that Scott's dad (JEFF GOLDBLUM) is a researcher who's trying to find a cure for human allergies to canines and Mr. Tinkles is concerned that if that occurs, dogs will have an upper hand in the perpetual battle between the two species.
Accordingly, the Persian ordered the removal of the Brody's dog and now has a contract on Lou, hoping to remove any canine presence so that he can put in a feline operative to retrieve Prof. Brody's formula and use it against the dogs. Fortunately for Lou, Butch (voice of ALEC BALDWIN), an operative for Dog Command, saves the young pup and introduces him to the world of canine spy operations, a James Bond like order where various dogs serve as agents and try to keep the peace using all sorts of high-tech equipment.
Lou then meets Butch's associates, Peek (voice of JOE PANTOLIANO), a Chinese hairless who's an electronics expert and watches for new cats showing up in the neighborhood, and Sam (voice of MICHAEL CLARKE DUNCAN), a friendly sheepdog who's a bit too enthusiastic about acting like a dog spy. As Lou tries to become accustomed to his new role as a dog agent on the lookout for felines, including Mr. Tinkle's lieutenant, Calico (voice of JON LOVITZ) and also meets Ivy (voice of SUSAN SARANDON), a stray Saluki hound who knows Butch from the past, he and other canines must contend with the nefarious cat's many attempts at removing them and stealing Prof. Brody's anti-allergy formula.