Nikolaus Fürst Esterhazy III. erwarb um 1809 zwei Häuser an der Walfischgasse, wovon eines das Haus „Zur weissen Lilie“ war, welches einst Helene Starhemberg, der Frau des legendären Grafen Starhemberg, dem Verteidiger Wiens, gehört hatte. Zum Zeitpunkt des Kaufes durch Nikolaus Esterhazy, gehörte das Haus „Zur weissen Lilie“ dem Grafen Sinzendorf. Die beiden Gebäude wurden abgerissen, und an ihrer Stelle entstand ein Wohnpalais im Empirestil. Bis in die 70er Jahre des 19. Jh. blieben die Esterhazy Besitzer des Palais. Dann wurde es von der Grafenfamilie Erdödy erworben. Ab 1911 wechselte das Haus noch zweimal die Besitzer, ehe im Zweiten Weltkrieg die Deutsche Reichspost sich in den Räumen einquartierte. Ein Bombenhagel gegen Ende des Zweiten Weltkrieges richtete beträchtlichen Schaden an dem Gebäude an. Um 1953 kaufte der Verein der Freunde des Wohnungseigentums das marode Gebäude, liess es abtragen und einen Neubau errichten.

Wie für die Palaisarchitektur der Empirezeit war das Haus gegen aussen hin ohne repräsentativen Prunk und wirkte eher schlicht, dafür vornehm. Umso reicher und glanzvoller war die Innenausstattung. Eine dreischiffige Einfahrtshalle mit Tonnengewölbe und Reliefarbeit führte in den Innenhof. Dort befand sich ein Hausbrunnen und darüber ein Löwenrelief. Das elegante Treppenhaus war mit einem einfachen Eisengeländer, glänzenden Marmorwänden und Säulen mit Palmettenkapitellen ausgestattet. Der grosse Festsaal war ein Meisterwerk empirischer Innenarchitektur: Es war ein grosser langgezogener Raum mit mehreren schweren Kristalllustern, einem kostbaren Parkettboden, Wandleuchtern, Marmorwänden und ornamentierter Decke. Das Palais Erdödy war eines der bedeutendsten Beispiele empirischer Innenarchitektur in Wien.