La Gran Depresión desatada por el crac del 29 también se extendió a Rumanía, afectando gravemente a la economía del país. Ante esta situación, el Gobierno rumano decidió pedir un préstamo al banco estadounidense Morgan, que obtuvo a cambio de esta transacción la concesión de un monopolio de veinte años de la telefonía rumana a la International Telephone and Telegraph Corporation (ITT),^[2]​ que entonces constituyó la Societatea Anonimă Română de Telefoane (SART, literalmente «Sociedad Anónima Rumana de Telefonía»)^[4]​ con el objetivo de modernizar la telefonía rumana y construir el Palatul Telefoanelor.^[2]​

Diseñado para la SART por el arquitecto rumano de origen holandés Edmond van Saanen Algi en colaboración con los estadounidenses Louis Weeks y Walter Froy, y construido en unos veinte meses entre 1931 y 1933, fue el primer edificio moderno importante de la Calea Victoriei de Bucarest,^[4]​^[3]​^[2]​ la calle sobre la cual Tudor Octavian escribió: «así es como se vería toda Bucarest si nos lo hubieran permitido [...], si sus constructores hubieran sido suficientemente inteligentes».^[5]​ Fue construido en la parcela que ocupaba previamente la mansión Oteteleșanu, que desde principios del siglo albergaba un bar con terraza (la Terasa Oteteleșanu), una cafetería y una cervecería, que competían con la Casa Capșa por la clientela de las élites de Bucarest debido a su cercanía al antiguo Teatro Nacional de Bucarest.^[2]​^[6]​

La estructura de acero fue producida por la fábrica de acero de Reșița. El edificio fue inaugurado en 1934 ante la presencia del rey Carlos II.^[2]​ El edificio fue ampliado (tanto vertical como horizontalmente) en 1940 y 1946, y sobrevivió a terremotos en 1940, 1977, 1986 y 1990, así como al bombardeo de las fuerzas aliadas en 1944, durante la Segunda Guerra Mundial.^[4]​^[3]​^[7]​ Con la llegada del régimen comunista, el edificio pasó a manos del Gobierno rumano, junto con la propia SART, que fue nacionalizada y transformada en una división del Ministerio de Correos y Telecomunicaciones. La Revolución de 1989 tuvo como resultado la fundación de la sociedad independiente ROM-POST-TELECOM, reorganizada como Romtelecom en julio de 1991.^[8]​

Un estudio de 1993 reveló problemas estructurales en el edificio, ya que la azotea no fue diseñada para soportar antenas de microondas, sino solo una cafetería. Antes de que en 1997 se iniciara un importante proyecto de reconstrucción, los ingenieros tuvieron que redibujar los planos del edificio, dado que los originales se habían perdido. Las obras incluyeron la restauración de la fachada original, además del refuerzo de la estructura. El proyecto de reconstrucción fue elaborado por el estudio de arquitectura rumano Proiect Bucuresti. Todo el proyecto, en el que trabajaron setecientas personas, costó aproximadamente un millón de euros y se prolongó hasta 2005.^[9]​

• Calea Victoriei between Casa Capșa and Palatul Telefoanelor, 1935, photo.
• Photo of Palatul Telefoanelor after reconstruction.