Wo im 18. Jrh. das erzbischöfliche Alumnenhaus stand, errichtete (vermutlich) Louis de Montoyer Stallungen, welche zum Palais Rasumofsky gehörten. Um 1828 demolierte man die Stallungen und erbaute das heutige Gartenpalais. Der Architekt Alios Ignaz Göll erhielt den Auftrag der Bauherren Leonhart Waller und Wenzel Emanuel Brandler von Brandenstein. Im Jahre 1851 erhielt das Gebäude einen Seitenpavillon. Fünf Jahre später erwarb Hugo Carl Fürst und Altgraf Salm.Reifferscheid das Palais vom vorherigen Eigentümer Erzherzog Carl. Um 1863 wurde das Gebäude baulich erweitert und inwendig umgestaltet. Der Fürsten blieb der Besitzer bis zu dessen Tod im Jahre 1902, worauf es in den Besitz von  Max Herzig kam, welcher Modernisierungen vornehmen liess.

Nach weiteren zwei Besitzerwechseln und unbeschadetem Überstehen des Zweiten Weltkrieges waren Privatpersonen die Eigentümer des Palais. Heute gehört es einer Privatperson und einem Architekturbüro. Das Gartenpalais im klassizistischen Stil mit dem Ehrenhof ist gegen die Gartenseite bedeutend aufwendiger gestaltet. Das Innere hat kaum Ursprüngliches erhalten können, bis auf vereinzelte Deckenmalereien und Supraporten. Das Stiegenhaus mit der schweren Holzvertäfelung ist sehr beachtenswert.