Wo das heutige Palais steht, befand sich im 17. Jrh. ein Lustgarten, wlcher Georg Ludwig Reichsgraf von Sinzendorf gehörte. Sein Besitztum wurde jedoch konfisziert, worauf Kaiser Leopold I. das Grundstück im Jahre 1686 Wolfgang Graf con Oettingen-Wallerstein zum Geschenk machte. Im Jahre 1769 kaufte Joseph von Egger das Grundstück, liess den Garten in Parzellen aufteilen und verkaufte eine davon an den Bierwirt Johann Georg Mayer. Dieser liess um 1777 ein eingeschossiges Gebäude bauen. Das Haus mit dem dazugehörigen Grundstück wurde um 1789 von Anton II. Fürst Grassalkovics gekauft und nach Plänen von Franz Duschinger zu dem heutigen Palais ausgebaut.

Das Haus hatte einst den Beinamen „Maria Theresien – Schlössl“, welcher aus der falschen Annahme hervorging, dass die Kaiserin Maria Theresia einst das Haus besass und es an den Fürsten verkaufte. 1793 wurde das Gebäude durch den Architekten Ernest Koch erweitert. Als der Erbe des Fürsten in finanzielle Not geraten war, musste er die Liegenschaft 1796 zwangshalber an das Bankhaus Arnstein, ein Gläubiger, verkaufen. Die spätere Besitzerin Barbara Storch liess das Gebäude um Seiten- und Quertrakte erweitern. Aus dem Palais wurde ein Mietshaus und war fortan Sitz unterschiedlicher Firmen, die hier untergebracht waren. Um 1991 erfolgte eine grundselegende Sanierung. Heute ist der Wiener Tourismusverband im Palais Grassalkovics eingemietet. Das klassizistische Gebäude, hat im Inneren durch die vermehrten Umbauten und Besitzerwechsel nichts von der ursprünglichen Ausstattung erhalten.