The film starts by featuring Misha Belenkoff (Tony Shalhoub) in his first night as the janitor at an animal testing lab. He used to be a literature teacher in Russia, but has been reduced to menial jobs after immigrating to the United States. His curiosity is piqued by a lone parrot, kept in isolation in the basement. He soon realizes that that parrot can do more than mimic sounds: he sings and talks, but only when away from observers. He gets the parrot to speak to him, but Paulie (voice of Jay Mohr) refuses to speak or perform for anyone else.
He eventually gets Paulie talking about his life story. Most of the rest of the narrative is told in flashbacks. His earliest memories find him as the pet of 5-year old Marie Alweather (Hallie Eisenberg). Marie is a stutterer. Her worried parents are pressuring Marie to start speaking properly. By observing the lessons, Paulie learns the meaning of words and how to construct complex sentences. He is then able to help Marie learn without pressure. Her stories about speaking to her parrot convince her father that Marie is unable to differentiate between fantasy and reality. He deals with this by selling the bird.
The next few years of Paulie's life are not depicted. He eventually finds himself at the pawnshop of the sarcastic Artie (Buddy Hackett). The films proceeds to follow Paulie's life under later owners and his efforts to locate Marie. The first such owner is the aging artist Ivy (Gena Rowlands). She teaches him a lot about life and putting things into perspective, but her health eventually takes a turn for the worse. The next owner is Ignacio (Cheech Marin), proud owner of a taco stand, entertainer and owner of trained parrots. Paulie learns to perform for an audience and falls for Lupe (voice of Tia Texada), a female conure. A misadventure lands him at the hands of petty criminal Benny (also Jay Mohr) and his girlfriend Ruby (also Tia Texada). They teach him the value of money and how to steal for them. Stealing from wallets and ATM machines proves easy, but his first attempt at burglary gets him captured.
He ends up at the institute. Dr. Reingold (Bruce Davison) promises to help him, but sees him more as a meal ticket. Paulie stops being so trusting and refuses to cooperate. This being the reason for his long isolation. Back to the present, Misha decides to help Paulie escape and find Marie. To their surprise, decades have passed. They find an adult Marie (Trini Alvarado), who is, regardless, happy to get her companion back.
