20 ноября 2003 года лидеры Молдовы и Приднестровья получили от МИД России новый Меморандум урегулирования приднестровского конфликта, разработанный Дмитрием Казаком, занимавшим в то время пост заместителя руководителя администрации Президента Российской Федерации. Суть российского миротворческого плана предполагала превращение Молдовы в федеративное государство с двумя субъектами федерации — Приднестровской республикой и Гагаузией. ПМР и Гагаузия получили бы особый статус и возможность блокировать законопроекты, нежелательные для автономий. Молдова обязывалась соблюдать нейтралитет и демобилизовать армию, а также предоставить России право на размещение российских войск на территории Приднестровья сроком на 20 лет в качестве «гаранта» урегулирования конфликта. Буквально в последний момент, под давлением ОБСЕ и студенческих протестов, президент Молдовы Владимир Воронин отказался от подписания соглашения, заявив, что оно дает односторонние преимущества ПМР и имеет скрытую цель — признание независимости Приднестровья.
Переговоры возобновились лишь в 2005 году на базе предложений, представленных украинским президентом Виктором Ющенко. Согласно новому плану до августа 2005 года парламент Молдовы должен был принять закон об особом статусе Приднестровья, по которому региону должны быть оставлены флаг, герб и три государственных языка — русский, украинский и молдавский. В случае, если Молдова перестанет быть самостоятельным государством, Приднестровье сможет выйти из ее состава В декабре 2005 года ПМР под контролем международных наблюдателей должна была провести досрочные выборы в парламент, а Молдова обязывалась признать их результаты. Затем Молдова и ПМР при участии России, Украины и ОБСЕ должны были провести разграничение полномочий между сторонами в рамках закона о статусе Приднестровья. Молдова должна была затем подписать международный договор, обязывающий ее исполнять закон о Приднестровье. Гарантами должны были стать Россия, Украина, ОБСЕ и, возможно, ЕСи США.
«План Ющенко» допускал прямое общение представителей мирового сообщества с ПМР без участия Молдавии. Документ не содержал требований вывода российского воинского контингента с территории ПМР, на котором настаивает Молдова.
22 июля 2005 года парламент Молдовы одобрил законопроект «О статусе Приднестровья». Согласно этому документу российские миротворцы должны были покинуть регион до 31 декабря 2006 года, а Приднестровье входит в состав Молдавии на правах автономии. Статус Приднестровья определен как «административно-территориальное образование в форме республики в составе Республики Молдавия».