Winkelpand op de hoek met het Singel, ontstaan uit de samenvoeging van vier verschillende panden.
Het deel op de hoek was oorspronkelijk Singel 239. Paleisstraat 16 stond ernaast; het had destijds de ingang aan de steeg halverwege de Paleisstraat, de Naaldenmakersgang. In 1887 werd het verenigd met het buurpand in de Naaldenmakersgang, Paleisstraat 14a. Opdrachtgever daarvoor was de weduwe Huffnagel, geboren Regenbogen, die er een café uitbaatte. Zij was destijds ook eigenaar van een hotel in de Plantagebuurt.
De winkel-woonhuizen Singel 239 en Paleisstraat 16 zijn op een ons onbekend moment verenigd. Dat was vóór 1909. In 1913 werden de panden verbouwd, in opdracht van eigenaar J.H. Muller: aan de Paleisstraat kwam een pakketpostdienst, en aan het Singel de ingang naar de bovengelegen kantoren.
Het geheel vouwde zich als het ware om Singel 237 heen. Dat huis werd in 1933 toegevoegd, eveneens in opdracht van J.H. Muller en in de stijl van het hoekdeel (architect: J. Dunnebier).
Het pand is de enige contemporaine herinnering aan de verbreding van de Korte Gasthuismolensteeg en de Stilsteeg tot Paleisstraat. De verbreding behelsde de afbraak van de huizen aan de noordkant van de stegen, en was in 1876 gereed. Het stadsbestuur wilde er de verbinding tussen Singel en Dam mee verbeteren.
Eerste bewoner van het winkelhuis Singel 239 was de kleermaker Eibert Lasthuis (Deventer 1820 - Amsterdam 1896), met zijn vrouw en kinderen. Zoon Nardus was ook kleermaker en mede-eigenaar van het bedrijf, en daarnaast actief in de Vereniging tot Heil des Volks.
Volgens het Monumenten Inventarisatie Project (MIP) was Lasthuis senior de opdrachtgever voor de bouw van het huis. Het MIP noemt verder als ontwerper J. Westhof. Ons is over hem niets bekend. Vermoedelijk wordt Jan Heshof bedoeld, een metselaarsbaas en makelaar op de Oudezijds Voorburgwal 324 die net als Lasthuis junior bestuurder was van "het Heil". De gevels vertonen veel overeenkomsten met het iets later door een andere Heshof ontworpen woonhuis aan het Tweede Marnixplantsoen.
Het gezin Lasthuis verhuisde in 1878 naar Singel 276. Hier kwam in 1881 een handel in boter en kaas met de naam Frisia, in 1886 gevolgd door een tabakswinkel.
In 1913 was er een slagerij gevestigd. Na de genoemde verbouwing werd het in 1914 een kantoor voor pakketpost van de landelijke posterijen. Het verving een houten hulplokaal op het Singel bij de Raadhuisstraat en werd vermoedelijk in de jaren 1920 gesloten.
De eerste gebruiker van de winkelruimte Paleisstraat 16 was de Alkmaarse sigarenfabrikant Joh.G. Stemler. Na enkele maanden opende hij een tweede winkel in Amsterdam, Kalverstraat 230. Stemler vertrok al snel. Na hem kwamen hier een speelgoedhandel, een boekhandel en in 1882 damesmodewinkel Au bon goût. Na het faillissement van de eigenaar in 1900 volgde nog een trits aan winkels, allemaal zonder veel succes: een Brussels advertentiebureau, een boekhandel, een conservenwinkel, een kunsthandel, een ondergoedwinkel uit Almelo, een winkel in aluminium keukenbenodigdheden, en diverse kledingwinkels.
De gehele begane grond is sinds 1984 een café. Aanvankelijk was dat Het Nieuwe Paleis (1984-1988); sinds circa 1991 heet het Het Paleis.
Paleisstraat 16, Singel 237-239
Er zijn 16 afbeeldingen in de beeldbank van het Stadsarchief die gerelateerd zijn aan dit adres.