Olive is a Christmas-loving dog who doesn't act at all like a dog. While in town, she meets Martini, a con artist penguin, from whom she buys a "Rolexxx". When she returns home from some errands, she finds her owner, Tim, putting away Christmas decorations and announcing morosely that there "won't be any Christmas".
Olive eventually finds out that this is because Blitzen, one of Santa's reindeer, is injured earlier during a practice flight and can not fly. Santa hopes he can make the Christmas run with "all of the other reindeer". Mishearing this on the radio as "Olive the other reindeer", Olive becomes convinced that it is she Santa is referring to, prompting her to travel to the North Pole to fill in on the sleigh team. On the way to the bus station, Olive runs into a grouchy Postman who is fed up with the stress of having to deliver the heavy loads of mail during the Christmas rush. ("Christmas (Bah, Bug and Hum)") He then tells Olive that "By next year, people will have forgotten about Christmas." He learns that Olive is trying to help save Santa's flight. He is vengeful towards Santa for being repeatedly put on his Naughty list and is determined to stop Olive from saving Christmas.
Olive goes to the "Mauvehound" bus station to buy a ticket to Arctic Junction. Martini shows up, and Olive buys him a bus ticket out of pity. Before they can leave the station, Olive is captured by the evil Postman, who tells people that Olive is wanted on several counts of mail fraud, such as "licking self-adhesive stamps and not mailing early for the holidays". After pleading to Martini to help her, Martini rolls several pens along the ground, tripping up the Postman. Martini and Olive then catch the bus right before it leaves, with the Postman watching them drive away.
On the bus, Olive and Martini talk to an Inuit couple and driver Richard Stans. They all believe Olive misheard Santa, but wish her luck anyway. The Postman pulls up next to the bus in his mail truck, but Martini fashions a paper airplane out of stationery, yells, "Deliver this, Punk!", and throws it at the Postman's ear, knocking him off the road. When they arrive at Arctic Junction, there is a one-hour wait for the next bus, so they go inside the restaurant for some food. The radio then says that Santa is scheduling a press conference for 11:00.The group does not know that their waitress is really the Postman in disguise. He lures Olive outside, saying that Santa is going to give her a flying test, then throws Olive inside his truck. While he is driving away, Olive finds a package addressed to her from "Deus Ex Machina." The package is a metal file Olive uses to escape. Olive then hears and sees a bus coming and tries to stop it, but fails. Olive then walks sadly to the Junction.
Back at the Junction, Martini then sees Olive and tells her that they found the waitress clothes and asks how Olive got away. Olive then asks Martini if he has heard of Deus Ex Machina. Then she Tells Martini that she missed the bus and he should've gone without him. Richard calls the postal service to complain about the Postman, but gets their voicemail. Richard says he is unable to continue taking Olive and Martini any further, because he is needed at the depot and does not want to lose his job, but still offers his support for Olive anyway before leaving. The two go inside the Top of the World Bar, and are initially harassed by the bar's patrons, including bar owner Round John Virgin and Schnitzel, Blitzen's flightless cousin, but Olive stands up to them before giving a heartfelt speech about the meaning of Christmas and how devoted she is to her cause. The patrons apologize for their behavior ("We're Not So Bad") and Round John Virgin offers Martini and Olive a ride to the North Pole in his vehicle, named The Polar Express. At the North Pole, Olive is denied entry to see Santa, but Martini gives the guard a watch as if it was a gift from Santa. When the guard asks Martini to fix it, he says he needs to kill the alarm, because the electromagnetic waves will interfere with the signal from a satellite. Olive digs under the fence, and proceeds to find Santa. Besides Blitzen's injury, Santa is not sure he wants to go out on Christmas Eve, after he reveals he has received mean-spirited letters from some children. Olive arrives and convinces him that the mean letters are really from the Postman, since they have no postmark. After introducing herself and persuading Santa not to give up on his mission, Santa thanks her for coming and Olive is put with the other reindeer to fly the sleigh.
Before they leave, the Postman switches the toy bag with his own bag of junk mail and kidnaps Martini. After the sleigh lands at the first house and Olive realizes what has happened, Olive uses the Postman's scent to track him and scares the Postman out of his wits as he sees Olive in the side window. After a struggle with the Postman, Olive gets pushed out, but Martini uses a jack-in-the-box to scare the Postman, who hits the window and is knocked unconscious. They retrieve the presents and rescue Martini, and then deliver the presents to the world ("Merry Christmas After All"). Lost in a fog, Olive guides them back to the North Pole by smelling the gingerbread cookies Ms. Claus baked. As a present, Olive is given a pair of antlers on a headband to wear. Comet gives her a ride home and Olive makes amends with Tim, who is glad that he does not care if she is different from other dogs.