Scheherezade was a witch who was turned into a cat by the Witches' Council like Salem, the latter of which she plans to marry so she can be turned back into a human.
Scheherezade first appeared in the Cat show where it was discover that she belonged to Harvey. Durng the competition she bested Salem out of everything including playing a piano. After winning first place Salem attempted to cast a spell on her only for her to deflected back to him.
After she left, Salem revealed to Sabrina that Scherezade is actually a witch, and also revealed that centuries ago when he had his human body and was going to ask her to marry him during a Anne Boleyn play but he chickened out and stood her up. When Sabrina force him to go out with her and after a few dates Salem couldn't commit to her and planned to leave her again.
But thanks to spell which makes Salem not afraid of commitment anymore (plus a dream of him and Scheherezade gmarried with two kids) Salem proposed to her. However Sabrina is told by Hilda that Scheherezade never went to the play centuries ago but to a party at Michelangelo's house and it was revealed she was turn into a cat because she stole the husband of Every Witch of the witches council.
Later with Sabrina went to Harvey's House she learned that once Salem says I do to Scherezade she'll return to her witch self and dump Salem. Later at the other Realm while she would waiting for Salem she and encountered Sabrina (who at the time use magic to turn into a yellow French cat) and after being tricked into being wooed she decided to marry the cat instead of Salem unfortunately when Sabrina change back to herself, ruining Scherezade's plan.