Первым построить переход через Керченский пролив путем сооружения запруды в начале XX века предложил Владимир Менделеев, сын химика Дмитрия Менделеева. В те же годы британцы планировали проложить железную дорогу в Индию по мосту через пролив. До стадии реализации эти проекты не дошли.
Строительство первого моста через пролив в 1943 году, во время оккупации Крыма, начали немцы. Мост был достроен после освобождения полуострова, но в феврале 1945 года не выдержал ледохода и рухнул.
В 1954 году пущена автомобильная и железнодорожная паромная переправа через пролив. В 1996 году из-за износа техники железнодорожное сообщение было прервано, но в 2004 году его восстановили.
19 ноября 1993 года в Москве вице-премьер РФ Александр Шохин, губернатор Краснодарского края Николай Егоров и представители французских компаний подписали протокол о намерениях о строительстве моста. Договор реализован не был.
20 августа 2000 года мэр Москвы Юрий Лужков и глава Верховного совета Крыма Леонид Грач подписали договор о создании АО «Керченский мост» для разработки проекта трехъярусного моста. По данным СМИ, узнав, что строительство оценивается в $0,5–1 млрд, стороны потеряли интерес к проекту.
В августе 2004 года власти Крыма сообщили о подготовке проекта подземного перехода под проливом стоимостью $780 млн, но утвержден он не был.
28 апреля 2008 года премьер Виктор Зубков сообщил, что министрам транспорта России и Украины поручено разработать предложения по строительству моста. В октябре того же года МИД Украины запретил финансирование проекта до согласования границ в проливе.
21 апреля 2010 года в Харькове о строительстве перехода договорились президенты Дмитрий Медведев и Виктор Янукович. 26 ноября минтрансы двух стран подписали с ВЭБом меморандум об организации строительства. Проект оценивался в $900 млн.
17 декабря 2013 года стороны подписали соглашение об организации строительства тоннеля или моста. В январе 2014 года кабинет министров Украины утвердил подписанное в декабре соглашение, стоимость проекта оценивалась в $1,5–3 млрд.