В 30-х годах XIX столетия возле комендатуры Владикавказской крепости был разбит сад, который стал называться Комендантским. Он занимал площадь верхней террасы современного парка. В начале 1840-х годов комендантом крепости генерал-майором П. П. Нестеровым были устроены верхняя часть парка «Монплезир» (франц. Моё удовольствие) и бульвар, который до 1888 года носил название Нестеровского. В 60-х годах XIX столетия сад стал называться как Городской парк.

Нижняя часть парка площадью 13 га начала создаваться в 1890-х годах, когда начальник штаба 21-й армии полковник М. Р. Eрофеев решил организовать в городе велосипедное общество. Вместе с единомышленниками он расчистил участок между Тереком и Александровским проспектом. Позднее он высадил там же деревья и кустарники, а затем устроил фонтан, веранду для оркестра, каток, горки для катания. В набережной части парка Ерофеевым из разросшихся деревьев были сформированы прекрасные тенистые аллеи с названиями «Аллея любви» и «Стрелка».

В начале 90-х годов XIX века в парке был устроен велодром, а 1-го апреля 1893 года состоялось официальное открытие «Общества любителей велосипедного спорта» (с 1911 года — "Спортивное общество «Трек»). С этого времени парк стал именоваться «Трек», и в нём регулярно проводились велогонки.

В середине 90-х годов XIX века, М. Р. Ерофеев передал парк в дар городу. По преданию, полковник похоронен в гроте посреди пруда. Возможно, именно поэтому, этот грот на почтовых открытках того времени именовался Ерофеевский.

В последующие годы в парке была создана система прудов с островами, лодочная станция, купальни. Парк постепенно стал называться «Монплезир».


Так два знаменитых русских военачальника, служивших на Кавказе, приложили руку к созданию старейшего парка Юга России, памятника культуры и ландшафтного искусства, включенного ныне в свод памятников ЮНЕСКО, и оба увязали это с любовью. К сожалению, имен тех прекрасных женщин мы так и не нашли.

В начале XX века в парке был сооружён зоопарк, в зимнее время пруды использовались как катки. В начале XXI века его закрыли. После Октябрьской революции парк стал называться «Пролетарский парк».

22 сентября 1939 года Пролетарский парк в связи с празднованием 80-летия осетинского поэта Коста Хетагурова решением Президиума Городского Совета города Орджоникидзе был переименован в парк имени
Коста Хетагурова.

Сейчас там можно наблюдать следующие исторические постройки (это не всё, но для меня значимое):