Своего рода стимулятором для сближения с Россией стала «евроизоляция» Л. Кучмы, начавшаяся в период «кассетного скандала» и усилившаяся в связи с международным скандалом по поводу якобы имевшей место продажи радарных систем «Кольчуга» Ираку. Именно Россия выступила с осуждением заявлений Совета Европы по поводу «дела Гонгадзе», назвав их покушением на суверенитет Украины.
Наиболее знаковым событием для украино-российских отношений начала 2000-х гг. стало подписание в сентябре 2003 г. в Ялте соглашения о Едином экономическом пространстве (ЕЭП) с Россией, Беларусью и Казахстаном (интересно, что история с «косой Тузла» началась немедленно после подписания этого соглашения). Соглашение в перспективе действительно сулило серьезные экономические выгоды, связанные с низкими таможенными барьерами, зонами свободной торговли и дешевыми энергоносителями. В то же время украинские политики небезосновательно усматривали в нем намерения России восстановить своего рода былой «единый народнохозяйственный комплекс», в котором она в силу естественных причин, была обречена на доминирующую роль. На это особо нажимала оппозиция, называвшая ЕЭП путем к утрате суверенитета (В. Ющенко). Именно поэтому Украина сосредоточилась лишь на одном компоненте ЕЭП как наиболее приемлемом варианте, а именно, на создании зоны свободной торговли. В апреле 2004 г. Верховная Рада первой из стран-участниц ратифицировала соглашение о ЕЭП с одной оговоркой — оно не должно было противоречить Конституции Украины. Эта формулировка открывала безграничные возможности для дальнейших дебатов и соответствующих обращений в Конституционный суд, не говоря уже о том, что начало президентской кампании заставило политиков, даже сторонников ЕЭП, быть крайне разборчивыми в своих суждениях относительно экономического суверенитета Украины.
Год подписания соглашения по ЕЭП был объявлен годом России в Украине — помимо серии культурных мероприятий, обычных для такого рода акций, он ознаменовался несколько курьезным эпизодом осени 2003 г., связанным с предложением российской стороны о пересмотре содержания школьных программ по истории, поскольку, по мнению российской стороны, украинские учебники по истории содержали ряд интерпретаций и утверждений, которые способствовали формированию негативного образа россиян и России (эти утверждения имели основания, так же как и претензии украинских историков относительно «украинских тем» в российских учебниках). Довольно стандартное предложение, отвечающее, кстати, стандартной европейской практике взаимных договоренностей, вызвало нестандартную реакцию — часть национальной интеллигенции восприняла это как попытку вмешательства России во внутренние дела Украины, как желание диктовать свою волю в переписывании истории. Был далее организован сбор подписей под воззванием к руководству страны прекратить какие-либо переговоры на эту тему (собственно, переговоров и не было).