Gordon Smith (DAVID ARQUETTE) is a mail carrier for the U.S. Postal Service who dreams about his neighbor, Stephanie (LESLIE BIBB), when not fending off dogs along his delivery route and hanging out with his friend and fellow postal worker, Benny Washington (ANTHONY ANDERSON). With Stephanie heading out of town on business and her babysitter being late, Gordon offers to watch her son, James (ANGUS T. JONES), until the sitter arrives. Stephanie reluctantly agrees, and Gordon soon finds himself with more than he bargained for when the sitter calls and states that she's sick and can't make it.
Meanwhile, on the other side of town, FBI agent Murdoch (MICHAEL CLARKE DUNCAN) is reluctantly watching as his canine partner, Agent Eleven, is taken off into the witness protection program. It seems that mob figure Sonny Talia (PAUL SORVINO) is upset that the proficient pooch foiled his latest criminal effort and permanently injured him, and has thus sent out his two goons, Gino (JOE VITERELLI) and Arliss (STEVEN R. SCHIRRIPA), to whack the dog.
Unbeknownst to Murdoch, the agent handling the protection program works for Sonny, and Agent Eleven barely escapes a run in with his armed henchmen. Seeking a place to hide, the dog spots Gordon's mail truck and zips into it, much to the delight of James who's accompanying Gordon on his route. The dog-fearing mailman obviously isn't happy about this, but after James starts crying when he plans to take the pooch to a shelter, Gordon reluctantly takes both the boy and his new dog home.
From that point on, and as Stephanie runs into various delays while trying to get back home and Murdoch tries to find his lost canine partner, Gordon and James try to get Agent Eleven to play and act like a normal dog, all while being unaware of his background or the mobsters' desire to find and do in the dog.