Nastasia is a character in the Wii video game Super Paper Mario. She is Count Bleck's right-hand minion and possesses the power to use hypnotic magic, which is most commonly used to turn allies of Mario into enemies. She is in love with Count Bleck and wants to replace Timpani as his love interest but is always denied. Apparently, she has command over Bleck's other minions, forcing O'Chunks to write an essay about Count Bleck and write and sing a song praising him as punishment for failing to stop Mario.
Nastasia was first seen in the wedding with Bowser, Peach, Count Bleck, Luigi and Bowser's troop. Nastasia hypnotizes Peach who insulted about the dress. Nastasia forces her to agree to marry Bowser, but Peach refuses. Nastasia hypnotizes her again that forced Peach to agree and the Chaos Heart summoned The Void.
- She is Count Bleck's only minion the player does not fight in the game, as she seems to lack the ability to fight.