“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. The player must restart the stage from this point for the Power Star. 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 remake of the old 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.
“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.”