La première mention de l'existence d'une demeure réservée à l'évêque de Toulouse date de la fin du VI^e siècle. Seule la présence d'un puits à l'intérieur de l'enclos de l'évêché, où vont boire les mules de l'évêque Foulque (1206-1232), est mentionnée à la fin du XII^e siècle.
Des travaux importants sont menés sous l'épiscopat de Pierre du Moulin (1439-1451). Celui-ci agrandit le palais par la construction d'une habitation sur la place Saint-Étienne. Son successeur Bernard de Rousergue ajoute un bâtiment sur la cour. Il fait bâtir une salle d'apparat au plafond orné de roses (ce sont ses armes), dans laquelle seront longtemps logés les rois lors de leurs visites à Toulouse.

Dalle gravée de Pierre du Moulin - photographie Daniel Martin. Ville de Toulouse, Musée des Augustins, Ra 414.

Au début du XVI^e siècle, Jean d'Orléans fait édifier à l'entrée de son palais une porte monumentale ornée de ses armes. Nous savons que sa demeure possède déjà une cour, un jardin et plusieurs dépendances, notamment les prisons et leur chapelle, des étables, des écuries et deux puits.

Plan Jouvin de Rochefort - Ville de Toulouse, Musée Paul-Dupuy. Bien que tous les corps de bâtiments de l'évêché ne soient pas représentés, ce plan donne une idée de la situation de l'évêché par rapport à la cathédrale. L'ensemble, organisé autour d'une cour et d'un jardin, est assez vaste.

A la fin du XVI^e siècle le cardinal de Joyeuse fait agrandir une petite galerie vers l'est pour relier l'archevêché à une maison dans laquelle seront logés quelques prêtres. Il s'occupe de faire aménager ses appartements privés et fait construire au-dessus de la grande salle une bibliothèque. Il aménage ensuite une remise à carrosse dans les écuries.

Croquis de la bibliothèque - Archives départementales de la Haute-Garonne, 1 G 935 n° 22.

Le cardinal de Joyeuse fait également des travaux dans la maison de la chapellenie, qui borde la place Saint-Étienne. Le mur de façade est réparé et agrémenté d'une « gélousie », sorte de pavillon en pierre qui donne à ce bâtiment le nom de « maison du balcon ». Celle-ci est rénovée et agrandie vers l'ouest au début du XVII^e siècle par l'archevêque Louis de Nogaret de Lavalette dans le but d'être louée.
Charles de Montchal (1628-1651) détruit les constructions devant l'archevêché et fait élever un long bâtiment sur le jardin pour s'isoler des voisins. La façade percée de grandes fenêtres en alternance brique et pierre est probablement construite pendant son épiscopat.

Certains éléments du logis du XV^e siècle ont été conservés dans le bâtiment actuel. Des pans de murs entiers, reconnaissables par leur épaisseur, subsistent au niveau de l'aile sur jardin et de l'aile est de la préfecture. En 1856, sous le parquet du petit salon de réception, le pavage de l'ancienne chapelle en carreaux emmaillés verts et blancs est retrouvé. Il s'agit d'un carrelage de la fin du XIIIe siècle.
Il semble que le logis épiscopal se présentait donc à la fin du XVII^e siècle comme un ensemble architectural disparate mais d'une grande richesse. Il se composait de plusieurs bâtiments d'époques différentes aménagés autour d'une cour et d'un jardin.