После указа Екатерины II от 5 мая 1785 года было создано Кавказское наместничество, возглавлявшееся вместе с Астраханской и Кавказской областями. В этих административных преобразованиях Ставрополь получил право быть одним из уездных центров Кавказской области.

История будущей главной улицы берет начало со 2 февраля 1786 года, когда в городе была учреждена гражданская власть — присутственные места и городской магистрат. Первым бургомистром стал купец 1-й гильдии Козьма Яковлев, а ратманом — купец 1-й гильдии Карп Колесников.

Одним из первых распоряжений новой власти стало официальное наименование трех улиц, тянувшихся с запада на восток: Первая, Вторая и Третья Мещанские. Сегодня этому соответствуют: проспект Карла Маркса, улица Орджоникидзе и улица Дзержинского.

Неофициально Первая Мещанская получила название Большой, а затем — Большой Тифлисской, поскольку с восточной оконечности улицы, у кордегардии (укреплённого поста), начинался известный Тифлисский тракт. В 1841 году здесь возводили «Триумфальную арку», которую также называли «Тифлисскими воротами», связывая сооружение с памятью о победе в войне 1812 года.

В архивных документах чаще встречается иное имя — Большая Черкасская: оно объяснялось тем, что рядом проходил тракт из Черкасска к Ставрополю, от столицы Донского казачьего войска. Этот путь шёл мимо стен ставропольской крепости и далее по направлению к улице Советской. Современники в 1799 году описывали эту «главную» на тот момент улицу неброско: «изрытую ямами для приготовление самана балку» с протекавшим ручьём и немногочисленными постройками, где выделялся каменный дом городского головы купца Волкова.

В начале XIX века описание оставалось схожим по тону: в 1802 году врач К. Бахутов отмечал «жалкий и дикий вид» Ставрополя, а улучшение связывал прежде всего с теми районами, где начиналось благоустройство. Однако импульс перемен усилился в середине столетия.

Когда в 1837 году Ставрополь готовился к визиту императора Николая I, было решено укрепить и расширить главный участок Большой улицы — от «Тифлисских ворот» до дома командующего войсками Кавказской линии и Черномории. Газета «Ставропольские губернские ведомости» сообщала, что «сотни топоров в месяц» завершили задачу: деревянные плахи и толстые доски должны были обеспечить проезжую часть. Параллельно засыпали ямы, где добывали глину, устроили ограждения, обновили тротуары и привели фасады в порядок.

К приезду императора появлялись и более «представительные» постройки. Среди них упоминаются дом интендантского чиновника Серова, где при присутствии Николая I открывали первую на Кавказе мужскую классическую гимназию, а также гостиница Найтаки — место остановки Лермонтова и его друзей-декабристов во время въезда Николая в город.

В 1851 году ставропольский генерал-губернатор Н. С. Завадовский направил рапорт наместнику Кавказа М. С. Воронцову с просьбой увековечить память о событиях 1837 года (пребывании Николая I) и о посещении Ставрополя цесаревичем в 1850 году. Предлагалось переименовать главную улицу в Николаевскую, а третью — в Александровскую (в тексте указано: речь о доме командующего войсками, где останавливался наследник). После этого площадь, ранее называвшаяся Воробьёвской, переименовали в Александровскую (с дальнейшим современным названием).

Дальнейшее благоустройство продолжалось. Летом 1856 года в Ставрополь доставляли строительные инструменты и материалы для работ по мощению и устройству городской инфраструктуры. Параллельно занимались ливневыми каналами, каптажом ручья и организацией безопасных переходов транспорта. В 1900 году Николаевский проспект мостили кубанским галечником, используя подрядные работы с подсыпкой песка, гравием в швах и трамбовкой.

К концу XIX — началу XX века проспект приобрёл характер «губернского центра»: вдоль него строились здания торгового и зрелищного назначения, а также сохранялись старые архитектурные объекты, включая Троицкий (Старый кафедральный собор) и церковь Спаса Нерукотворного. Здесь же размещались учреждения административного характера — от дома губернатора до Ставропольской контрольной палаты.

Революционные события изменили и городскую топонимику. В 1920 году большевики переименовали Николаевский проспект в улицу Красную. Позднее, в связи с переносом центра Орджоникидзевского района, улица получила имя И. В. Сталина. С конца 1960-х проспект стал носить имя Карла Маркса.

История улицы показывает, как в её названиях и облике отражались политические повороты и развитие города — от трактовой функции и триумфальных символов до благоустройства и архитектурного «лица» губернского центра. И сегодня, как звучит в авторской позиции, есть идея вернуть одной из старейших магистралей Ставрополя её историческое имя — Николаевский проспект.

Краткая хронология названий:
— до начала XIX века: Первая Мещанская улица;
— неофициально: Большая Тифлисская улица, Большая Черкасская улица;
— до 1851 года: Николаевский проспект;
— до 1920 года: Красная улица;
— до 1937 года: Проспект Сталина;
— до 1962 года: Проспект Карла Маркса;
— с 1962 года: (уточняется в источнике авторской версии).