Zwischen Stephansplatz, Rotenturmstraße und Wollzeile befand sich der 1276 urkundlich genannte Pfarrhof von St. Stephan mit einer urkundlich 1271 genannten Kapelle. Es war das ein großer, ungegliederter Bau mit einem mächtigen Turm an der Ecke Rotenturmstraße–Stephansplatz.
Nach der Erhebung von St. Stephan zur Propstei unter Rudolf IV. wurde der Name Propsthof üblich. Im Jahre 1627 brannte die Gebäudegruppe aus. Der rechtmäßige Bischof Melchior Clesel war von Ferdinand II. nach Rom abgeschoben worden und so geschah vorerst nichts.
1631, nach dem Tode Clesels, wurde der kunstsinnige Abt von Kremsmünster, Anton Wolfrath, der erste Fürstbischof von Wien. Er ließ nun als bischöfliche Residenz den Bischofshof neu errichten. Als er 1639 starb, vollendete Friedrich Philip Graf Breuner, sein Nachfolger im Bischofsamt, den Bau.
Es war das ein verhältnismäßig einfacher frühbarocker Bau mit rustiziertem Sokkelgeschoß, einer im 3/8 Schluss gegen den Stephansfreithof vorspringender Kapelle und einem schweren rustizierten Portal gegen die Schauseite – die Rotenturmstraße – hin. Baumeister war nach Überlieferung ein sonst nirgends genannter Architekt Giovanni Coccapani. An der Ecke Stephansplatz-Rotenturmstraße befand sich, zwischen Mesnerhaus und Palais, das Mesnertor zum Stephansfreithof. So war die Fassade gegen den Dom eine Nebenfassade. 1 716 wurde Sigismund Graf Kollonitsch Bischof. Er beschloss, das Palais modernisieren zu lassen. Ausgenommen blieb lediglich die Kapelle und das Portal.
Aus der Zeit vor der Neugestaltung hat sich eine Zeichnung von Ehrenberg anlässlich der Überführung der alten Pummerin (josephinische Glocke) nach St. Stephan aus dem Jahre 1711 erhalten. Sie zeigt die Hauptfassade. Diese ist wohl gut gegliedert, doch fast schmucklos. Charakteristisch für das 17. Jh. sind die schweren Ortsteine gegen die Wollzeile. Neben dem Haupttor sind an den Ecken zwei weitere rustizierte Portale zu sehen.
Bei der Neugestaltung wurden nun Fensterbekrönungen geschaffen – sie sind denen des Erweiterungsbaues der böhmischen Hofkanzlei verwandt – und über dem Portal das Kollonitschwappen mit dem erzbischöflichen Hut angebracht. Da Wien 1 723 zum Erzbistum erhoben wurde, ist das Jahr der Auftragserteilung dafür gegeben. Ein Kupferstich nach Salomon Kleiner von 1 725 zeigt bereits die heutige Fassadengestaltung.
Gegen den Stephansplatz zu ist die Fassade folgendermaßen gegliedert: Links und rechts von der vorspringenden (3/8 Schluss) Kapelle befinden sich je sechs zweigeschossige Fensterachsen. Das erste Geschoß ist rustikaartig genutet, das zweite Geschoß ist glatt.
Die Kapelle trägt den Schmuck der Erbauungszeit. Auf jeder der drei vorspringenden Kapellenseiten befindet sich ein großes, rund geschlossenes Fenster, das Mittelfenster trägt einen rund geschlossenen Giebel mit Blumenvase und Putto, die seitlichen Dreiecksgiebel. Im Bogen unter den Fenstern sind schwere Festons mit Granatäpfeln, entsprechend dem Stil um 1640. Der Eckrisalit ist dreigeschossig. Das zweite Geschoß hat Fensterbekrönungen wie die Hauptfassade, Voluten und Muscheln.
Die Hauptfassade gegen die Rotenturmstraße ist völlig symmetrisch, dreigeschossig und hat 13 Fensterachsen. In der Mitte, über der Torzone eine Doppelfensterachse, rechts und links davon je sechs Achsen. Uber dem Doppelfenster des zweiten Geschoßes befindet sich das Wappen des Bischofs Sigismund Kollonitsch, im Keilstein des Tores ein Patriarchenkreuz. Über den Säulen der Portalzone befinden sich Ziervasen, ebenfalls Zutaten von nach 1 716. Besonders wirksam sind die Bekrönungen der Fenster des zweiten Geschoßes. Die Fassade gegen die Wollzeile ist wieder einfacher gestaltet.
1869 wurden an der Domseite Geschäftslokale eingerichtet. Ebenso in der Wollzeile. Hier wurde auch ein einfaches Tor geschaffen, das heute der Eingang in das Palais ist.
Im Inneren befinden sich zwei durch den Bibliotheksflügel getrennte Höfe. Der Bibliotheksflügel ist mit 1641 bezeichnet. Die Arkaden im Inneren sind größtenteils vermauert. Prachtvoll ist das Treppenhaus mit dem durch Stuckputten verzierten Aufgang zu den Repräsentationsräumen gestaltet. Zarter Stuck, leicht getönt, ziert diese Räume.
Aus der Erbauungszeit stammt der Stuck in der Andreaskapelle. An der Westseite des Bibliotheksflügels ist der aus dem 1 7. Jh. stammende Hausbrunnen mit einer Statue.
