Sheraton uppfördes på kvarteret Snäckan i samband med den omfattande Norrmalmsregleringen som kraftig förändrade Stockholms innerstad och området kring Tegelbacken. Tidigare fanns i detta kvarter bland annat Nya Banken mellan 1912 och 1920. Söder om nuvarande Sheraton, mitt på Tegelbacken, låg Kronprinsens stall. I denna byggnad låg caféet Tysta Mari som gett namn åt den överbyggda gångväg (Tysta Marigången) som går genom kvarteret i bottenplanet. Arbetet med att bygga det nya hotellet var en del av den genomgripande ombyggnaden av Tegelbacken som pågick 1959–1971.
Huset ritades av AOS Arkitekter och uppfördes 1969-1971. Hotellet har nio våningar plus takvåning och har en brunröd fasad i glaserat fasadchamotte mot Vasagatan och Tegelbacken, mot Herkulesgatan brun sprutputs. Gårdsfasaden har vit sprutputs och på gården finns en portal bevarad från Wredeska palatset.[4] Fasadplattorna har en storlek av 50x50 cm respektive 70x30 cm och levererades av Iföverken i Bromölla.[5]
En omfattande invändig renovering genomfördes 2007 där hela interiören byttes ut och bland annat den klassiska pianobaren försvann, konferensutrymmena utökades och rummen byggdes om. [3]
Under våren 2007 genomfördes en omfattande inventering av fastigheterna på Norrmalm som uppfördes mellan 1960 och 1989 av Stadsmuseet i Stockholm. Bebyggelsen klassificeras i fyra kategorier efter deras kulturhistoriska värde. Sheraton var ett av de fjorton hus som fick en blåmarkering, vilket innebär "att bebyggelsen bedöms ha synnerligen höga kulturhistoriska värden".[6]
