It is commonly reported that Ruxelana came from Rohatyn in Ukraine (Rohatyn was part of Poland prior to WW2) where they have a statue of her in the city square. However I did read suggestions that that origin is apocryphal and really it is not clear where exactly in Eastern Europe she was from. So what is known of her origin?
The Wikipedia article on her says "According to some historians, Roxelana was born as Aleksandra Ruslana Lisowska", implying there is some doubt or uncertainty if that is her birth name. Are there any records or sources that link Roxelana to this birth name?
At the time she was enslaved, how far north did the Ottoman Empire extend into Eastern Europe? Was Rohatyn part of the Ottoman Empire at the time?
You're right that the historical consensus is that she probably came from Rohatyn, in Ruthenia. This town was part of the Polish-Lithuanian state at the time; today it is in western Ukraine.
But it’s important to stress that the evidence for all of this is pretty late. Mikhalon Litvin – a Lithuanian writing in about 1555 – had heard the story in its essentials, writing: “The most beloved wife of the present Turkish emperor – mother of his primogenital [eldest son] who will govern after him, was kidnapped from our land.” But it was the Polish poet Samuel Twardowski who put most of the flesh on the bones of the story as it’s told today. Twardowski served as secretary of a Polish embassy to the Ottoman Empire in 1622-23. He picked up his information from conversations at the Turkish court. See Galina Yermolenko [ed.], Roxelana in European Literature, History and Culture (Farnham: Ashgate, 1988) p.2&n. According to Yermolenko,
“Roxelana is believed to have been born in the western part of Ukraine around 1505. Sometime between 1515 and 1520, when she was around 15 years of age, she was abducted by the Crimean Tatars on one of their slave raids… She most probably followed the route that thousands of her compatriots followed in the sixteenth century – walking in long caravans of captives to the biggest slave market in the Black Sera region, Caffa… She then appeared in the Avret Pazari (“Women’s Bazaar”], a slave market in Istanbul, and, according to legend, was purchased for the imperial harem by Ibrahim Pasha, a close friend of the young Crown Prince Suleiman. Ibrahim presented her to Suleiman, probably before the latter became Sultan in 1520. Her playful temperament and great singing ability soon won her the name of Hurrem [the “joyful” or “the Laughing One”], and that was probably what attracted Suleiman’s eye. She quickly became Suleiman’s favourite concubine, ousting from that position the beautiful Circassian concubine Mahidevran, the mother of Suleiman’s first-born son Mustafa.”
Mustafa was killed on his father’s orders in 1553 after word spread that the son was planning to assassinate the Sultan, leaving Roxelana’s son Selim to inherit the Ottoman throne. Yermolenko cites a Polish work published in 1861, Poezye Samuela z Skrzypny Twardowskiego, as her source for all this.
I wrote in more detail about the Crimean Tatars and their slave raids in the Ukraine here: