Объект культурного наследия регионального значения «Каменный мост» построен в 1826 г. на пересечении улиц Старо-Московской (Карла Маркса), Воскресенской (Орджоникидзе) и Богословской (Чернышевского). К началу XIX века особенно остро встала проблема благоустройства Воскресенского спуска. Со времен строительства Азовского флота по спускавшейся к реке Богословской улице шел поток грузов к военным верфям. Место здесь размывалось водой и постепенно образовался овраг, который очень близко подходил к перекрестку улиц Старо-Московской и Воскресенской, мешая проезду. В распутицу это место становилось очень опасным и, по свидетельству мемуариста, воронежского архитектора С.И.Соколова (1802-1868), в народе его прозвали «волчьей ямой»: или потому, что многим довелось здесь «тонуть», или от того, что рядом находился «Дом архитектора И.И. Волкова» (ул. К. Маркса, 43).
При воронежском губернаторе Николае Ивановиче Кривцове (1794-1843) началось активное благоустройство города. 16 июля 1826 г. Н.И. Кривцов обратился в Хозяйственный департамент Министерства внутренних дел за разрешением на строительство моста, при этом он предоставил проект, выполненный городским архитектором И.А.Блицыным.
Блицын И.А. (1780-е гг. – после 1841 г.) – городской (1819-1831), губернский (1831-1835) архитектор. Кроме каменного моста по проекта И.А. Блицына построены Всесвятская кладбищенская церковь (1836-1851, не сохр.), городская дума и магистрат в г. Павловск Воронежской губернии (1824), церковь Иоанна Богослова в г. Богучар Воронежской губернии (1836-1846), Никольская церковь на Архиерейской даче на берегу реки Дон (1841, не сохр.), перестроил дом Д.В. Черткова под Дворянское депутатское собрание (1822-1824, не сох.). С 1835 – первый в Воронеже «вольнопрактикующий архитектор».
Не дожидаясь разрешения из Петербурга, губернатор приказал начать работы. Мост был построен в августе – сентябре 1826 г. Стоимость работ составила 5596 рублей. За строительство моста без утверждения в инстанциях проекта и сметы генерал-губернатор А.Д. Балашев объявил Н.И. Кривцову, уже оставившему пост воронежского губернатора, выговор. Новому губернатору Б.А. Адеркасу было предписано освидетельствовать необходимость постройки моста и его прочность. Комиссия в составе: губернатор Б.А. Адеркас, губернский архитектор Т.С. Кондратьев, городской архитектор И.А. Блицын, городской голова Клемешов, летом 1828 г. осмотрела мост, отметила прочность и настоятельную необходимость его постройки для города. Заключение комиссии спасло Н.И. Кривцова от грозившего ему денежного начета.
При строительстве моста был благоустроен перекресток улиц Старо-Московской и Воскресенской: уровень улиц повышен насыпью, при этом Воскресенская улица изменила свое направление, стала проходить рядом, овраг углубили и он выводил на Богословскую улицу. Богословский спуск выровняли для удобства проезда, возвели подпорные стены, замостили булыжником дорогу. Таким образом, у моста сформировался сложный перекресток с подпорными стенами и лестницами на спуске под Воскресенской церковью. Во второй половине XIX века на мосту и под мостом установили керосиновые фонари. Вблизи моста стояла полицейская будка.
Вновь выстроенный мост был первым в Воронеже мостом, сложенным из кирпича («камня»), отсюда он получил наименование «Каменный мост».
В 1984–1986 гг. к 400-летию города была проведена реконструкция моста, выполненная по проекту архитектора А.В. Поспеева. Вопрос реконструкции каменного моста рассматривался Воронежским филиалом института «Гипрокоммундортранс». По свидетельству конструктора филиала И.Березина на момент реконструкции каменный мост находился в «хорошем состоянии, тревогу вызвала подпорная стена, сложенная в 19 веке, с течением лет она наклонилась к дороге…» Конструкции моста были укреплены. Для усиления подпорных стен были использованы бетонные блоки. Вдоль моста и откосов вместо глухого оштукатуренного парапета была установлена чугунная решетка. На пилонах в концах моста установлены чугунные торшеры и металлические доски с надписью “400 лет” (надписи были демонтированы, предположительно, в начале 2000-х гг.).
Работы были произведены строителями РСУ-1 треста «Воронежремстрой» и городского комбината благоустройства.
В начале 1980-х годов перед началом реконструкции вдоль конструкций моста были проложены трубы системы наружной теплотрассы, исказившей архитектурный облик памятника.