“I need a good head on my shoulders. Do you know of anybody in need of a good body? Please! I'll follow you if you do!”
Despite his name, the Headless Snowman has never been seen to be decapitated, although his body once melted away during the events of Super Mario 64 (in the stage Snowman's Lost His Head, to be exact). Thankfully, Mario (or Yoshi, Luigi, or Wario in Super Mario 64 DS) is searching for Power Stars on the mountain at the time and assists the snowman (who is looking for nearby headhunters) by rolling down a huge snowball fit to be the Headless Snowman's new body. However, running into him will cost the player three health points. If the player isn't by the head when the body starts rolling towards it, it will miss the head entirely and fall off the stage, and The player must restart the stage from this point for the Power Star. If Mario is by the snowman's head, the body will run into the head and complete the snowman itself. If this happens, the happy snowman gratefully awards the hero with just the thing he was looking for, a Power Star.
The Headless Snowman reappears in Super Mario 64 DS, with the same role as the original game. In this appearance, he is given facial expressions. Without the rest of his body, he gets a sad face but when he gets his body back, he gets a smile. He also appears in the minigame Snowball Slalom, in that same game and in the New Super Mario Bros. version of that game.
Once this mission is complete, the snowman will remain with a full body in one spot during every mission (unless the player does Snowman's Lost His Head again).
“Oooooh nooooo! Talk about out-of-body experiences--my body has melted away! Have you run in to any headhunters lately?? I could sure use a new body! Brrr! My face might freeze like this!”
“Perfect! What a great new body! Here--this is a present for you. It's sure to warm you up.”