“'I do'. Say it now, K?” —Nastasia, Super Paper Mario
Nastasia is Count Bleck's secretary and right-hand woman. She manages the other minions and has great hypnotic power. At the end of the game, she saves him from Dimentio, blocking Count Bleck from a seemingly fatal blast. At the start of the game, she uses her hypnotism to force Princess Peach to marry Bowser, so that Bleck can crash the wedding and kidnap Bowser, Peach and Luigi for his plan involving the Dark Prognosticus. During the course of the game she falls in love for Bleck but knows she could never measure up to Timpani (Tippi). Nastasia, though never fought in the game, is still a boss for many reasons. Her hypnotic power hypnotized not only Mr. L but the rest of the "Bowser Organization" well known as the Koopa Troop, Bowser's army. Basically you are fighting her through half the the enemies of the game. So, as you're swearing under your breath after you've just got run over by a turtle wearing dark sunglasses, you can thank her. Oh, and she also controls all of the other minions, punishing them if necessary for failing to defeat Mario or any other unsatisfactory behavior.
If you talk to Carson the guy who owns the bar in Flopside, he speaks of a tale called, "Of Bats and Men". He says the tale is true, but he does not understand the meaning. It is a story of a man looking for his lost love. On the way there, he spots a bat stuck in a trap. He sets it free, and it flies away. Later, after he returns to his campsite, he is greeted by the bat, who immediately turns into a woman. She pledges her life to him and agrees to follow him wherever he goes. This is most likely talking about Nastasia and Count Bleck, with his lost love being Timpani.
There have also been other rumors that Nastasia could have been the pixl queen in the first paper mario game. However, these rumors have been nullified due to the fact there is no evidence proving that this is true.
Nastasia begins her hunt to locate and hypnotise all the escapees. She is about to hypnotise Peach when the princess is mysteriously teleported away.
Nastasia and Bleck agree to send "him" to the hero of prophecy.
Nastasia is not seen again until Mario and Co. infiltrate Bleck's Castle. She is seemingly murdered by Dimentio, but ends up on the third floor of Flipside, where Mario informs her that Count Bleck has been reunited with his former love, Tippi.
- Nastasia seems to bear some similarties to Jolene.
- Nastasia is the only member of Count Bleck's group that the hero never fights in the story.