В одночасье сфера влияния Российского государства расширялась до Днестра, являвшегося южной границей Брацлавского полка запорожцев. Данный тектонический сдвиг в международных отношениях просто не мог ни коснуться Молдавского княжества.
Уже в феврале в Яссы прибыл российский посол Гавриил Самарин с грамотами от царя. Самодержец пожурил недавно восшедшего на престол господаря Георгия Стефана за то, что тот не известил Москву о начале своего правления. Кроме того, молдавский правитель получил предостережение от оказания помощи польскому королю в борьбе против запорожского войска Богдана Хмельницкого.
Такое послание было ясным сигналом молдавским элитам, что Россия становится активным участником международных отношений к северо-западу от Черного моря и с ее интересами следует считаться.
Российские интересы в тот период требовали дистанцирования других государств от вмешательства в польско-украинское противостояние на стороне Кракова (древней столицы Польши). Между тем после Переяславской рады Молдавское княжество, как и другие вассалы турецкого султана, были обязаны выполнять волю Порты и оказывать содействие полякам.
Тем не менее в Яссах российскому послу был оказан очень теплый прием. Миссия Самарина далее продолжилась в Валахии, а Стефан направил в Москву своего посла Ивана Григорьева.
Молдавский посол (русинского происхождения) прибыл в столицу России в апреле 1654 года и передал царю грамоту, в которой господарь просил покровительства. От имени молдавского монарха посол сделал устное заявление, в котором также просил царя принять "его под свою государскую руку, так же как и гетмана Богдана Хмельницкого и все войско Запорожское".
В ответной грамоте Алексей Михайлович заявил о согласии принять Молдавию под покровительство России. Вместе с тем российской дипломатии было поручено выяснить, "подлинно ли молдавский владетель Стефан ищет российского подданства".
Хмельницкому же стало известно об участии отрядов молдавского войска в военных действиях с запорожцами на стороне поляков, а также о разглашении господарем царского послания, доставленного Самариным. В своем письме в Москву гетман делал вывод, что Стефан-воевода "никакова добра его царскому величеству не мыслит".
Мотивом таких действий Георгия Стефана было, скорее всего, стремление поддерживать хорошие отношения с обоими соседями, противостоявшими друг другу в начинавшейся русско-польской войне за Украину.
Возобновление русско-молдавских дипломатичных контактов произошло лишь весной 1656 года. К тому времени Речь Посполитая находилась на грани полного разгрома. В ее прибалтийских и западных владениях хозяйничали шведы. Войско под командованием Хмельницкого и русского воеводы Василия Бутурлина пройдя вдоль молдавской границы дошло до Львова.
Господарь Георгий Стефан смог реабилитироваться в глазах русского царя тем, что оказал активное содействие налаживанию отношений между украинским гетманом и трансильванским князем. За молдавского господаря в Москве ходатайствовали православные Иерусалимский и Антиохийский патриархи.
В итоге представительной молдавской делегации было дозволено явиться в Россию. Ее возглавили митрополит Гедеон и логофет (глава господарской канцелярии) Григорий Ненул. Это было самое многочисленное посольство за всю предыдущую историю молдавско-российских отношений (31 человек).
Прибыв в мае 1656 года в Москву, митрополит и логофет преподнесли грамоту — прошение от имени господаря "и всей молдавской земли к благочестивому царю и самодержцу". Документ был датирован 15 марта и содержал просьбу о принятии Молдавии в российское подданство, предоставляя полномочия делегации на ведение соответствующих переговоров.
После того как состоялась аудиенция у царя, посланцы были приглашены в Посольский приказ. На сей раз русские дипломаты запросили гарантии, что предложение молдавского господаря является действительно искренним. В ответ им были предъявлены ходатайства упомянутых патриархов. К примеру, Макарий Антиохийский ручался за Стефана и угрожал проклятием господарю и всей молдавской земле, если они ослушаются царя.
За Молдавию также просили московский патриарх Никон и гетман Хмельницкий.
Летом 1656 года были выработаны условия принятия Молдовы "под руку царя". Основные договоренности заключались в восстановлении доосманских молдавских порядков, назначении на должность господаря только уроженца Молдавии, возврате под власть княжества крепостей и земель, захваченных турками и татарами, участии молдаван в войнах против Османской империи. Также Молдова освобождалась от уплаты дани, а молдавским купцам разрешалось вести торговлю в России.
После того как условия присоединения были согласованы царем, 17 июля в соборной церкви Успения Пресвятой Богородицы патриарх Никон привел к присяге митрополита Гедеона. Позднее состоялась присяга логофета Ненула и других членов молдавской делегации.
Посольство вернулось в Яссы в январе 1657 года, однако российские посланники, которые должны были привести к присяге самого господаря, в Молдавию так и не прибыли.
Причины тому крылись в резком ухудшении для Москвы международной обстановки.
Осенью 1656 года обострились отношения между Хмельницким и московским правительством. Гетман был недоволен условиями Виленского русско-польского перемирия и решил продолжить собственную войну против Речи Посполитой. Кроме того, шла напряженная русско-шведская война. В этих условиях у Москвы оставались крайне призрачные возможности защитить Молдову в случае османского вторжения.
Господарь Григорий Стефан был низложен султаном в марте 1658 года. Покинув родину, он обосновался в померанском Штеттине и активно занимался созданием антитурецкой коалиции христианских государств.
Последующие события на Правобережной Украине, вторжение туда османов на время отодвинули границы России от молдавских рубежей. Тем не менее в 1656 году был создан прецедент официального обращения о вступлении молдаван в российское подданство.
Через пол столетия аналогичное соглашение было достигнуто Дмитрием Кантемиром и Петром I. Затем в ходе русско-турецкой войны 1735-1739 годов российский генерал Миних принимал в Яссах присягу у молдавских бояр императрице Анне Иоановне.
По мере усиления России к западу от Днепра все больше молдаван становились российскими подданными. Создание военно-поселенческой провинции Новая Сербия, организация Бугского казачьего войска, хозяйственное освоение Приднестровья и Бессарабии — это лишь самые крупные совместные достижения Российского государства и выходцев из Молдавского княжества.