Der Architekt Ludwig Richter, ein Schüler des Ringstrassenarchitektes Theophil Hansen, entwarf in den Jahren 1886 bis 1889 für Max Graf Vrints zu Falkenstein ein späthistoristisches Palais. Das Palais mit seinen französisch-klassischen Formen wurde zum Hauptwerk Richters und gilt als eines der prächtigsten Beispiele des Wiener Barockhistorismus. Baumeister war Alois Schuhmacher. Nachdem ab 1905 zuerst die Familie von Redlich und darauf Dr. Friedrich Haymerle des Palais besassen, wurde es schliesslich vom griechischen Staat erworben, welcher noch heute die Botschaft in Österreich darin untergebracht hat.
Für die Errichtung des Palais Falkenstein wurden Natursteine aus den Steinbrüchen von Kaisersteinbruch und St. Margarethen verwendet. Der grosse Mittelrisalit wird dominiert von sechs riesigen korinthischen Halbsäulen. Das schlichte Rundbogenportal ist in der Mitte angebracht. Die Statuengruppe auf der Attika, welche die von zwei allegorischen Figuren umgebene Göttin Nike darstellt,  stammt vom Bildhauer Emanuel Pendel.

Sehr markant ist das riesige Haubendach, welches dem Palais seine charakteristische Erscheinung verleiht. Das Treppenhaus mit seinen Hermenpilastern und dem grossartigen Eisengeländer ist eines der prachtvollsten Teile des Palais Falkenstein. Ebenfalls prächtig ist der Speisesaal, welcher mit reichem Stuck ausgestattet ist und in dem noch immer der grosse Kristalluster aus der Entstehungszeit des Palais hängt.