Построено на участке, принадлежавшем в прошлом роду Трубецких, выкупленным перед Первой Мировой войной страховым обществом "Россия" под застройку; на участке были заложены фундаменты под доходные дома. В 1922 г. участок передан Наркомпочтелю (НКПиТ СССР, будущий Наркомсвязь СССР) под постройку на нём центральной телеграфной станции.
9 сентября 1925 г. Московское архитектурное общество объявило открытый всесоюзный конкурс на проект здания. В конкурсе участвовала 21 работа.
Хотя первую премию присудили Александру Гринбергу, Наркомпочтель заказал ещё два проекта вне конкурса — Алексею Щусеву и Ивану Рербергу. По мнению современных исследователей, самый яркий конструктивистский проект предложил именно Щусев. Однако его идею отклонили, поскольку предложенное сплошное остекление фасадов не соответствовало условиям конкурса. В результате строительный комитет Моссовета порекомендовал выбрать проект Рерберга и с этим предложением согласилось руководство Наркомпочтеля.
В 1925 г., сразу после одобрения проекта, началось возведение здания на дореволюционном фундаменте. Через два года строительство было завершено и началась установка техники, продлившаяся ещё столько же. На первом этаже Центрального телеграфа располагались машинное отделение, телеграфные и телефонные залы, библиотека, а также раздевалка и столовая, на втором — канцелярия. Третий и четвёртый этажи занимали аппаратные залы. Официально здание называлось «Дом связи им. В. Н. Подбельского». В газетах Центральный телеграф именовали «механизированным дворцом связи».
После введения здания в эксплуатацию в его стенах разместились четыре организации: Центральный телеграф, Центральный радиоузел и отделения междугородной и международной телефонной связи.
В 1941 году помимо Центрального телеграфа в здании размещались Наркомат связи и Центральная междугородная телефонная станция.
Во второй половине XX века Центральный телеграф сохранил ключевое значение в качестве коммуникационного центра СССР.
В настоящий момент владельцем здания является ПАО «Центральный телеграф» — дочерняя компания «Ростелекома», которая сдаёт площади в аренду различным организациям, никак не связанным с почтовой и телеграфной деятельностью. Почтовое отделение и телеграф выехали из здания в начале 2019 г., Министерство связи — в марте 2019 г.
Площади в здании сдаются в аренду под различные нужды. Ожидается масштабная реконструкция здания в многофункциональный комплекс.
Объект культурного наследия народов РФ регионального значения. Рег. № 771310006650005 (ЕГРОКН).