В 1908 году городская дума приняла решение о строительстве нового, большего размера здания для Главпочтамта[2]. Трёхэтажное кирпичное здание на Евдокимовской улице было построено в 1913 году по проекту городского архитектора П. П. Шмидта[3]. Здание строилось Торговым домом «Шаевич и Бару» из Ростова-на-Дону под управлением инженера Ивана Богданова[4]. Эта же строительная компании оборудовала канализацию и отопление[5]. До настоящего времени сохранился аутентичный логотип этой строительной фирмы на входе в почтовое отделение. Строительство здания велось за счёт городского бюджета, стоимость строительства составила около 100 тысяч рублей[4].
24 июля 1913 года члены комиссии во главе с городским главой Гаппо Баевым подписали акт приёмки здания и передачи его почтово-телеграфной конторе[6]. В здании также располагалось управление телефонной сетью, которое ранее вместе с центральной почтово-телефонной станцией находилось на Михайловской площади (современная площадь Свободы) на месте современного Дворца юстиции[4][6].
На первом этаже нового здания находилась почтовое отделение, кабинет помощника начальника, различные кладовые, денежная, посылочная, помещение для переходящих и разборных почт, помещение для приема телеграмм и почтовые ящики абонентов. На втором этаже располагались телеграф, кабинет начальника и его канцелярия, аппаратная, Бодо-зал и аппаратная Юза, различные технические помещения, мужская и дамская уборные, библиотечная комната и класс. На третьем этаже находились жилые квартиры начальника конторы и его помощника[5].
В 1920-х годах XX века на торце здания был оборудован экран РОСТа (плакаты со стихотворениями В. Маяковского)[3][2].
В настоящее время в здании действует почтовое отделение 362040.
Киреев Ф. С. По улицам Владикавказа. — 2-е изд., доп. и перераб. — Владикавказ: Респект, 2014. — 189 с. — ISBN 978-5-905066-18-4.
Торчинов В. А. Владикавказ : Краткий историко-краеведческий справочник. — Владикавказ: Северо-Осетинский научный центр, 1999. — 221 с. — ISBN 5-93000-005-0.
Цаллагов С. Ф. Владикавказ — летопись в камне. — Владикавказ: Веста, 2008. — 136 с.