Op 4 september 1826 opende Pantaleon Gerhard Coenraad Hajenius in hotel De Rijnstroom aan de Dam bij de hoek met de Halsteeg zijn tabaks - en sigarenwinkel. In 1868 werd de zaak - ‘betrekkelijk den Handel in Sigaren en het fabriceren en verkoopen van Tabak en Snuif’ - verplaatst naar een andere plek aan de Dam, als gevolg van de verbreding van de Halsteeg tot de huidige Damstraat. Het bedrijf floreerde, behaalde steeds meer diploma’s en medailles op internationale tentoonstellingen en verwierf een grote vermaardheid. Het huis Hajenius ontwikkelde zich tot hofleverancier van vele Europese vorsten. In 1914 was de firma wederom genoodzaakt te verhuizen, nu voor de bouw van het kledingmagazijn Peek & Cloppenburg, naar de huidige vestiging aan het Rokin. Een jaar later werd de zaak met de nodige luister geopend.
Het nieuwe gebouw van Hajenius werd ontworpen door de gebroeders Van Gendt A.Lzn. Het bestaat uit een functioneel en voor die tijd modern betonskelet met een traditioneel vormgegeven exterieur van natuursteen. De opbouw wordt zowel horizontaal als verticaal geleed. De verdiepingen rusten op een ‘sokkel’ die wordt afgesloten door een kroonlijst. In de bovengevel benadrukken gestileerde pilasters het verticale accent. De voorgevel is bekleed met Oberkirchener zandsteen, terwijl de borstwering van de winkelpui is voorzien van graniet. Boven de entree bevindt zich het gebeeldhouwde koninklijke wapen, een verwijzing naar het destijds gevoerde predikaat ‘Hofleverancier’. In de gevel herinnert de naam De Rijnstroom nog aan de vorige vestigingen van de firma. Op de verdiepingen kwamen kantoorruimten en een conciërgewoning.
Het rijke en stijlvolle interieur, eveneens ontworpen door de gebroeders Van Gendt, is nagenoeg geheel origineel en gaaf bewaard gebleven. De wanden en de toonbanken zijn bekleed met diverse soorten marmer en voorzien van houten panelen en decoratief bronswerk. Het gedecoreerde en in goud - en bronskleur geschilderde plafond is plaatselijk ingedeeld in vakken. Aan het plafond zijn twee kroonluchters van messing bevestigd. De grote tabakspotten op de schappen van de vitrines zijn gemaakt van Delfts aardewerk en daarna beschilderd met Chinese voorstellingen.
Bij de opening van de winkel was in het pand een even verfijnd achterkamertje opgenomen, bedoeld ‘om met zorg ’t allerfijnste van al die kostelijke geurigheid te proeven’. Menige klant had bij Hajenius ‘reserve’ staan, zoals dat heette: als iemand een sigaar bijzonder waardeerde , liet hij 1000 of 2000 stuks voor zich wegzetten om daarna van tijd tot tijd een kistje te komen ophalen. In het oorspronkelijke magazijn van de firma, rechtsachter de winkel, bevinden zich twee fraaie met houtwerk ingelegde sigarenvitrines. In deze ruimte met de rondlopende galerij worden van tijd tot tijd bescheiden exposities gehouden.