Der Ursprung des Gebäudes dürfte zurückgehen ins Jahr 1276, als der Pfarrhof von St. Stephan erstmals urkundlich erwähnt wurde. In der Zeit von 1469, als Wien von Kaiser Friedrich III. zum Bistum erhoben wurde, bis zur Ernennung Wiens zum Erzbistum im Jahre 1723, wurde das Gebäude „Bischofshof“ genannt. Später erhielt es die Bezeichnung „Probsthof“. Um 1579 wurde das Haus nach auftrag von Bischof Caspar Neubeck ausgebaut und verschönert, beim grossen Stadtbrand von 1627 jedoch wieder komplett zerstört. In den Jahren 1632 bis 1641 entstand das heutige Palais unter Bischof Anton Wolfrath und Philipp Graf Breuner nach den Plänen von Giovanni Coccapani.

Bis 1640 war ein Wehrturm seitens der Wollzeile Teil des Palais, welcher jedoch niedergerissen wurde, um den Bischofshof zu vergrössern. Als 1723 Bischof Siegmund Graf Kollonitsch zum Erzbischof ernannt wurde, wurde das Haus folglich erzbischöfliches Palais. Erst gegen Ende des 19. Jrh. erhielt das Gebäude das obere Stockwerk auf der Seite der Rotenturmstrasse. Im gleichen Zuge wurden die Räumlichkeiten im Erdgeschoss mit den Rundbögen gegen den Stephansplatz hin für Geschäfte freigegeben.

Heute beherbergt das Palais die Residenz des Kardinals, die Verwaltung der Erzdiözese Wien und das 1933 gegründete Dom- und Diözesemuseum. Auffallend ist der hervortretende gotische Chor der zum Palais gehörenden Andreas-Kapelle, welche im Jahre 1638 erneuert und umgebaut wurde und an der Stelle eines alten Vorgängerbaus aus dem Jahre 1271, der Achatiuskapelle, steht. Bis Ende 18. Jrh. hatte die Kapelle einen Turm, der dann abgerissen wurde. Das Innere ist reich verziert mit Stuckdekor. Der Renaissance-Altar stammt aus der Augustinerkirche. Um 1716 wurde die Fassade des Palais gegen die Rotenturmstrasse hin reich verziert mit Stuck und anderen Zierelementen. Dem barocken Treppenhaus folgen eindrückliche Repräsentationsräume mit Stuckdecken aus dem Jahre 1716. Im der hauseigenen Bibliothek befinden sich kostbare Büchersammlungen und Urkunden aus mehreren Jahrhunderten.