29 октября 1851 года молодой граф Толстой посетил крепость Владикавказ по пути в Тифлис для поступления на военную службу. Его зачислили в 20-ю артиллерийскую бригаду, которая базировалась в станице Старогладковской на Тереке. Здесь же, на Кавказе, Толстой начал свой творческий путь, принесший ему всемирную известность.

Вскоре после смерти Льва Николаевича городская Дума Владикавказа постановила: в целях увековечения памяти великого писателя переименовать улицу Моздокскую в улицу графа Толстого. Это название она носит и по сей день.

Главной достопримечательностью этой улицы была немецкая лютеранская кирха, которая находится на углу улиц Толстого и Миллера (до революции – ул. Гимназическая). Сегодня в ее здании находится Концертный зал филиала Мариинского театра в РСО–А.

Роль немцев в жизни дореволюционного Владикавказа была значительна. На 1910 год в городе проживало более 600 немцев, в основном представители интеллигенции: врачи, учителя, инженеры, офицеры. В Терской области было несколько немецких колоний: Михайловская, Гнаденбург, Эммаус, Каррас и другие. При кирхе действовало одноклассное лютеранское училище. Но в целом улица Толстого "немецкой" не являлась. Здесь проживали горожане различных национальностей: Папков, Митрофанов, Карлашев, Кцоев, Колосовский и другие.

Галантерейными магазинами на этой улице владели Л. Куплевацкий, Б. Пералов, аптеками – Лашин и Лукаш. В 1916 г. на углу улиц Толстого и Яшина (до августа 1915 г. – ул. Низовая) выстроил одноэтажный дом известный владикавказский фотограф, родственник и друг Коста Хетагурова Александр (Садулла) Джанаев-Хетагуров. После его смерти здесь продолжала жить его семья, пока в 1930 г. дом не был муниципализирован и вдова фотографа, ее больная дочь и двое сыновей, трудившихся простыми рабочими, не оказались на улице. Вот такая печальная история…