Активно предлагать Европейскому союзу безвизовый режим Россия начала в 2002 году в связи с так называемой калининградской проблемой. В преддверии вступления в ЕС Польша и Литва должны были серьезно ужесточить контроль на границах, что усложняло транзит по их территории в российский эксклав. Москва предлагала в качестве одного из вариантов разрешения ситуации распространить на Россию режим шенгенской зоны. Брюссель согласился дать россиянам только возможность проезда в Калининград с упрощенными транзитными документами.
Главным аргументом европейцев было отсутствие между сторонами договора о реадмиссии — возврате нелегальных эмигрантов. Соответствующее соглашение было подписано 25 мая 2006 года на саммите Россия--ЕС в Сочи. Однако Брюссель на этот раз согласился лишь на некоторое упрощение визового режима. Новые правила вступили в силу 1 июня 2007 года. Главным их достоинством стало значительное смягчение порядка получения краткосрочных, сроком до 90 дней, виз в страны ЕС. Однако туристов новые правила не касались. В дальнейшем Москва несколько раз выступала с инициативами об отмене виз, однако, как отмечал глава МИДа Сергей Лавров, "не чувствовала никакого встречного энтузиазма".
В июне 2010 года в ходе саммита Россия--ЕС в Ростове-на-Дону российские дипломаты передали партнерам ранее не обсуждавшийся проект "Соглашения об отмене визовых требований для граждан РФ и ЕС". Этот ход Москвы оказался для европейцев настолько неожиданным и малоприятным, что они несколько месяцев отказывались официально его комментировать.
В апреле 2011 года было объявлено, что российские и европейские дипломаты согласовали "Перечень совместных шагов", предваряющих подписание соглашения об отмене виз. Тогда стороны заявляли, что в окончательной редакции текст документа должен быть принят руководством Евросоюза и России на саммите в Нижнем Новгороде 9-10 июня.