The Postman is an evil mailman who is fed up with the stress of having to deliver the heavy loads of mail during the Christmas rush. He is vengeful towards Santa for being repeatedly put on his "Naughty" list and is determined to stop Olive from saving Christmas. His first attempt is forcefully abducting her from the bus terminal while pretending to evoke a citizen's arrest on her for "mail fraud", only to be foiled by her penguin ally Martini. He pursues their bus in his van and attempts to ram it, only to be once again foiled when Martini tosses a paper airplane to throw the Postman off their path. He reappears at the truck stop between the United States and the North Pole under the (rather poor) disguise of a waitress. The Postman tricks Olive into believing that she has been summoned by Santa for a flying test and kidnaps her in the parking lot. He entraps her in his van, although she escapes thanks to a gift from "Deus ex Machina".
Not beaten, the Postman reappears and tries to sabotage Santa's Olive-assisted route by swapping his toy bag for a bag of junk mail. The Postman also abducts Martini and keeps him prisoner in the van. He flees but Olive manages to catch his scent and pursue him. After a struggle, Martini throws The Postman off with a jack-in-the-box. Olive then gets the right bag back from The Postman who is then tied up and left in his van.
In the end, Martini is shown taking over his job as a postman while The Postman is given to the City Zoo as a "penguin" for their exhibit.