Настасья Окульевна является одной из героинь славянских сказаний о богатыре Михайло Потыке. Она спасла его от происков бывшей жены, Марьи Лебеди белой. История такова. Пока богатырь Михайло Потык сражался с врагами в чистом поле, Марья стала возлюбленной царя и уехала с ним. Вернувшись, богатырь бросился за ними в погоню, попадая по пути в ловушки хитрой жены: пил сонное зелье-вино, проваливался в глубокую яму, был превращен в горючий камень.
Михайло Потык, герой былин о Лебеди белой и Настасье Окульевне, художник Иван Билибин, 1902
В последний раз, опоив богатыря зельем, распяла Марья его в подвале на каменной стене и оставила умирать. Тогда-то и спасла Потыка сестра царя Настасья Окульевна. Она смогла снять оковы, излечила богатыря от ран, достала хитростью саблю, богатырскую палицу и доброго коня. Возвратился Михайло к царским палатам и убил бывшую жену вместе с царем. Женился на Настасье Окульевне и стал править.