Мост, именовавшийся в проекте по неофициальному названию отрезка Невского проспекта между площадьми Восстания и Александра Невского Старо-Невским, был сооружён в 1960 - 1965 годах под руководством группы инженеров во главе с Александром Семёновичем Евдониным и группы архитекторов во главе с Александром Владимировичем Жуком. По некоторым сведениям, он должен был выглядеть гораздо более нарядным, однако, его создатели были вынуждены следовать постановлению ЦК КПСС и Совета министров СССР от 4 ноября 1955 года "Об устранении излишеств в проектировании и строительстве" и разработали максимально упрощённый дизайн переправы.
Открывшийся накануне 48-й годовщины Октябрьской революции 5 ноября 1965 года мост (1 ноября по нему с целью проверки прочности прошла колонна танков) получил имя национального героя России, государственного деятеля и полководца Александра Невского (1220 или 1221 - 1263). 15 июля 1240 года в результате кровопролитного сражения на реке Неве (Невская битва) новгородская рать во главе с князем Александром Ярославовичем разгромила шведские войска Биргера Ярла, пытавшиеся взять под свой контроль древний торговый путь "из варяг в греки". В 1710 году на месте, считавшемся тогда полем Невской битвы (в действительности же, она произошла гораздо выше по течению Невы, в устье реки Ижоры), Пётр I основал монастырь - нынешнюю Александро-Невскую лавру. В 1788 - 1790 годах архитектор Иван Егорович Старов разбил перед монастырскими воротами Александро-Невскую площадь (с 1923 года - Красная площадь, с 1952 года - площадь Александра Невского), от которой и был проложен на правый берег Невы новый мост.