Единственный сын казнённого господаря, будущий великий Молдавский правитель – Стефан III Великий (1429 – 1504) укрылся в Валахии, в соседнем княжестве. Он был уже зрелым воином и, видимо, несмотря на молодость, обладал зачатками сильного и волевого правителя. Стефан III сумел сплотить вокруг себя противников узурпатора господаря Петра III Арон и в апреле 1457 года с шеститысячным войском вторгся в Молдавию. В двух сражениях он разгромил Петра III, который бежал в Польшу. Власть в Молдавии перешла к Стефану III.

Новому господарю досталось тяжёлое наследство. Положение Молдавии было очень нестабильным. Ослаблением Молдавии стремились воспользоваться её грозные соседи, прежде всего короли Венгрии, традиционно считавшие Молдавию сферой своего влияния. Не прочь утвердить на Молдавском престоле своего ставленника, были правители Польши. Но наибольшую опасность представляла Турция. Однако Стефану III удалось постепенно упрочить свою власть, обуздать строптивых бояр и создать сильное войско.

Мать Елены Стефановны – княгиня Евдокия Александровна Олелько происходила из литовского великокняжеского рода. Родоначальником литовских князей является великий Литовский князь Гедимин Великий, правивший в 1316 – 1341 годах. Он оставил большую семью. Его сыновья стали родоначальниками многих литовских и русских княжеских фамилий, таких как – Трубецкие, Голицыны, Куракины, Хованские в России, Чарторыйские, Сангушко, Полубинские в Литве и Польше.

Один из внуков Гедимина Литовского – Владимир Ольгердович (умер 1398), получил в удел южнорусские земли. Он был удельным князем Киевским, а после получил во владения города Слуцк, Копыль и Бельск. Свои земли он передал сыну Александру (умер 1454), более известному под именем Олелько. Это прозвище закрепилось за его потомками.

Род князей Олельковичей, раздевшейся на две линии, по своим владениям, одна линия владела Киевом, другая Слуцко-Копыльским княжеством, занимал привилегированное положение в Великом Литовском княжестве. Олельковичи, как представители старшей линии Гедиминовичей, претендовали на Литовский великокняжеский престол, пользуясь поддержкой шляхты, особенно в южнорусских землях. Известно несколько попыток оппозиционно настроенной к королевской династии Ягеллонов шляхты передать престол Олельковичам. Однако все они закончились неудачей. А после очередного участия в заговоре против короны в 1481 году Олельковичи потеряли права на Киев, но смогли удержать Слуцк и Копыль.

Кроме того, князья Олельковичи имели давние связи с Северо-Восточными русскими княжествами, в том числе и с Москвой, и считались ревнителями православной веры в южной Руси.

Род князей Олельковичей угас в 1593 году, Слуцкий удел по женской линии перешёл в род литовских магнатов Радзивиллов.

Князь Александр-Олелько был женат на княжне Анастасии Васильевне Московской (умерла 1470), дочери великого князя Московского Василия I Дмитриевича и княгини Софьи Витовтовны Литовской. Таким образом, Елена Стефановна состояла в дальнем родстве со своим мужем Иваном Молодым.

Брак Стефана III с княгиней Евдокий Олельковной Слуцкой был династическим. Молдавский господарь, утвердившись на престоле, чтобы противостоять своеволию бояр и пользовавшегося покровительством поляков свергнутого господаря Петра III нуждался в поддержке. Поэтому для уравновешивания сил искал союза с литовскими князьями, как противовес польскому влиянию. К тому же княгиня Евдокия Слуцкая была православной христианкой, что, очевидно, было немаловажным фактором.

Княгиня Евдокия Александровна была второй женой господаря Стефана III. Их брак состоялся после вступления Стефана III на престол 4 июня 1464 года. Известно, что его первой супругой была некая Марыска, очевидно Мария. Кто она была неизвестно. Скорее всего, Марыска происходила из Валахии, где скрывался после гибели отца Стефан III, и происходила из простого или мало-знатного рода.

О рождении и детстве Елены Стефановны в источниках нет никаких сведений. Даже неизвестна точная дата её рождения. Она могла родиться в период между 1465 – 1467 годами. Свадьба Стефана III и княгини Евдокии Олелько состоялась 5 июля 1464 года. Как сообщает Бристрицкая летопись: «В лето 6971 года прият Стефан воевода себе господжда княгиня Еудакия от Киева, сестра Семёна царя». А в 1467 году княгиня Евдокия Александровна умерла. Впервые в молдавских источниках Елена упоминается 10 мая 1466 года. При исследовании скелета Елены было установлено, что она прожила 40 – 45 лет. Умерла Елена Стефановна 18 января 1505 года, так что можно предположить, что родилась она, вероятно, в конце 1465 года.

О детских годах Елены, о её воспитании в источниках так же ничего не сообщается. Она рано стала наполовину сироткой. А так как её отец господарь Стефан III был вынужден постоянно вести войны со своими соседями, особенно долгой и напряженной было противостояние с турками, то уделять много времени дочери он не мог. Поэтому маленькая Елена, или как её называли на молдавский лад Илинка, находилась на попечении мамок, то есть нянек.

Не имея наследников мужского пола, господарь Стефан III в 1472 году женился в третий раз на гречанке Марии из Мангупа (умерла 19.12.1477), происходившей из Крыма. Их брак был недолгим. Мария Мангупская умерла в 1477 году, родив двух сыновей, умерших в детстве.

Известно, что овдовев, Стефан III в 1478 году взял в жёны Марию Бассараб (умерла 1511), дочь Валашского господаря Раду III Красивого и Марии Деспины. Получается, что Елена росла под присмотром двух мачех, так что рассчитывать на большую материнскую любовь и заботу не могла.

Начавшиеся родственные связи Мушатинов с Русью, браком Елены Волошанки и Ивана Молодого, хотя и не были особенно приоритетными, но продолжились и в последующие годы. Праправнук Стефана III Великого – господарь Богдан IV Лапуштяну, лишённый престола турками в феврале 1572 года нашёл убежище в Москве. Он был с почётом принят при царском дворе и наделён Лухским уделом. Богдан IV умер в Москве, завещав Молдавский престол русскому царю Ивану IV Грозному. Его двоюродный брат Иоанн III Лютый (умер 14.06.1574), прежде чем занять Молдавский престол в 1572 году, шесть лет жил в России. В Москве он женился на русской княжне Марии Семёновны Ростовской.

Наследственные права Мушатинов, ослабивших свою власть в результате кровавых междоусобиц, на престол в Молдавии были нарушены в конце XVI века. С этого времени всё чаще власть, с санкции турок, оказывается у временщиков. Последним Мушатином на Молдавском троне был Илиас Александру (умер 1675), правивший в 1666 – 1668 годах. Он уступил престол очередному турецкому ставленнику Георгию Дуки и поселился в Константинополь.

Стефан III заняв Молдавский престол, получил ослабленное и экономически разорённое государство. Молдавия была крохотной страной в окружении могущественных соседей. На севере Молдавия граничила с Польским королевством, на Западе с Венгрией. Венгерские короли постоянно пытались установить свой контроль над Молдавией, поэтому господари искали помощи у поляков, номинально признав над собой власть польской короны. Но самым опасным было южное направление. Молдавии постоянно угрожали крымские татары и турки.

Турки ещё в 1396 году завоевали Болгарию, в 1459 году окончательно подчинили Сербию, в 1453 году заняли столицу Византийской империи город Константинополь. Таким образом, Турция вплотную придвинулась к молдавской границе. Турецкий султан подчинил Валахию, небольшое княжество, граничившее с Молдавией, добившееся независимости с первой половине XIV века, выйдя из-под контроля Венгрии. Турки обрушились на Валахию. Валашский господарь Мирча Старый (1386 – 1418), мужественно отразил турецкое вторжение, но после, оказавшись без поддержки европейских монархов, в 1415 году вынужден был признать себя данником турецкого султана.

Расправившись с Валахией, турки перенесли свою агрессию на Молдавию. Ещё в 1420 году произошло первое турецко-молдавское боевое столкновение. Со временем турецкая опасность только увеличивалась. Поэтому, перед лицом столь грозного противника, Молдавия должна была объединиться под властью одного правителя.