Долгое время территория Нижневолжской набережной имела название Нижнего посада и хаотично застраивалась торговыми, складскими и жилыми зданиями. После череды пожаров и попыток перестройки был создан «план с лучшим порядком и прочностью».
В первой половине XIX века начал формироваться современный облик улицы. Отныне разрешалось строить только каменные дома, в то время как набережная расширялась и укреплялась. Со временем на улице выросли каменные казармы, торговые дома, биржа и дистанции — небольшие здания, в которых находились на карантине прибывавшие грузчики.
Нижневолжская набережная проектировалась в 1830-е годы архитекторами Иваном Ефимовичем Ефимовым и Петром Даниловичем Готманом.
В 1836 году были начаты работы по благоустройству набережной, к которым ежегодно привлекалось до 2850 человек и 750 телег. Надзор над проектом осуществлял инженер-капитан Дмитриев. Земля для подсыпки берега доставлялась с копки Зеленского и Похвалинского съездов. Чтобы насыпной грунт не уносило паводком, берег было решено обложить булыжным камнем, который привозили в Нижний Новгород из Ярославской и Костромской губерний.
В 1836 году каменную обкладку набережной подрядился выполнить крестьянин Климов. В 1838 году Нижневолжская набережная была отделана булыжником под руководством инженера Николая Ивановича Лика в рамках больших работ по благоустройству города, начатых по личным указаниям Николая I. После этого впервые в истории Нижнего Новгорода вдоль городского берега стал возможен проезд на транспорте.
Коренным образом начал меняться и облик Нижнего базара. На набережной отныне разрешалось строить исключительно каменные дома. Первую каменную усадьбу в этом районе возвели князья Голицыны.
В 1841 году паводок повредил 111 саженей набережной. Ремонт стоимостью 3000 рублей провел все тот же крестьянин Климов. Впоследствии столь значительных разрушений набережной уже не наблюдалось. В 1909–1911 годах была проведена намывка берега и дополнительная обкладка булыжником.
В XIX веке Нижний Новгород жил рекой, поэтому здесь находились причалы пароходных обществ «Кавказ и Меркурий», «Самолет», братьев Каменских.