På tidigt 1930-tal räckte inte postutdelningen på Vasagatan till och Posten bestämde sig för att bygga Posthuset på Kungsholmen. Erik Lallerstedt hade tio år tidigare ritat Posthuset Odengatan och fick uppdraget för även denna postbyggnad. Bygget påbörjades 1936 och stod klart 1938 med Posten som byggherre och fastighetsägare. Resultatet blev en slätputsad funkisfastighet med glasade utbyggnader och en indragen ingång med neonskylt ovanför.

Från början var det tänkt att det skulle vara bostäder högst upp enligt tidigare traditioner i andra posthus i Stockholms innerstad. Efter en riksdagsdebatt 1936 där det skulle anslås medel till bygget röstades förslaget ned och Kungliga Byggnadsstyrelsen fick då i uppdrag att utreda möjligheterna för hur de fem översta våningsplanen ovanför posten kunde nyttjas för annan statlig verksamhet.