Ursprünglich gehörte das Grundstück des heutigen Palais dem Nonnenkloster Maria Porta Coeli, was übersetzt in etwa Maria zum Tor des Himmels heisst. In dieser Bezeichnung hat die heutige Himmelspfortgasse ihren Ursprung. Zu den frühen Besitzern des Vorgängergebäudes des Palais gehörten bürgerliche Personen. Um 1587 kaufte der kaiserliche Rat und Hofkriegszahlmeister Egidi Gattermeier, Ahnvater der Grafen von Gatterburg, das Anwesen. Dessen Nachkommen verkauften das Haus  um 1625 Paul Freiherrn von Rákóczy von Felsö-Dobaz. Dieser bewohnte das Palais Ende des 17. Jrh. Besitzer waren jedoch seine Schwester Juliane und sein Schwager, Feldmarschall-Leutnant Ferdinand Gobert Graf Aspremont-Reckheim. Die Erbin Elisabeth Rákóczy übertrug den Besitz des Palais im frühen 18. Jrh. ihrem Ehemann Georg Graf Erdödy, der oberste Landrichter Ungarns. In den Jahren 1720 bis 1724 liess dessen Nachkomme, Georg Graf Erdödy von Monyokerek das heutige Palais errichten.

Der Architekt ist unbekannt. Um 1773 kaufte Joachim Egon Landgraf von Fürstenberg das Gebäude. Für eine kurze Zeit wohnte Ludwig van Beethoven in dem Haus und widmete der Hausherrin einige Kompositionen. Der Landgraf liess um 1825 das Innere des Palais dem damaligen Stil anpassen. Die Familie fürstenberg blieb im Besitze des Palais bis in Jahr 1987, als es von einer Privatperson erworben wurde. Im Gegensatz zur majestätischen Ausstattung des Portals mit darüberliegendem Balkon erinnert die Fassade des Palais eher an ein barockes Bürgerhaus als an einen Adelspalast. In der Beletage befinden sich die Repräsentationsräume mit beachtlichem Stuckdekor.