Les fresques de la voûte ont été réalisées entre 1509 et 1512. Des cartouches peints précisent même l'avancée du chantier : à la 5e travée, on lit la date de 1510 alors que celle de 1511 est peinte à la 6e, 7e et 8e travée. Les suivantes montrent le millésime 1511.
Le chantier a progressé d'est en ouest. Les quatre premières travées furent peintes en 1509 -la date figure dans la 3e chapelle nord- aux frais du cardinal Louis II d'Amboise dont les armes figurent en abondance dans cette partie de la voûte. Les travaux sont prolongés après sa mort (novembre 1510) par son successeur Charles de Robertet dont le blason se remarque sur la partie occidentale des voûtes et sur les parois des chapelles.
L'atelier de peintres qui réalise le décor de la cathédrale d'Albi est originaire d'Italie. Il se compose surtout de peintres originaires de Bologne et quelques-uns ont laissé leur noms. Ainsi aux chapelles 7 et 8 sud, dans un cartouche à la voussure de la fenêtre et sur la voûte de la chapelle 12 nord, on lit celui de Giovanni Francesco Donela, de Carpi. D'autres noms (huit au moins) ont été repérés en divers endroits, permettant d'estimer que l'atelier était constitué d'environ une dizaine d'artistes.
Après 1512 et jusqu'en 1520 l'atelier poursuit son travail dans les chapelles comme le prouvent les dates relevées dans certaines d'entre elles : 1512 (chapelles 6 nord et 12 nord), 1513 (chapelles 7 nord, 12 nord, 7 sud et 14 sud), 1514 (chapelle 9 sud) , 1520 (chapelle 14 nord).
Le style des peintures rappelle celui du Quattrocento avec le souci de couvrir une vaste surface. La narration théologique et pastorale est concentrée dans un petit nombre de scènes alors que l'essentiel de la surface est recouvert de rinceaux habités. Le sens du volume et de l'espace se manifeste dans la représentation des personnages isolés et dans les scènes représentées sur les panneaux au centre de la nef.
Le programme figuré illustre, en miroir de la statuaire du choeur, l'histoire de l'humanité, de l'Alliance, de l'Eglise et du salut. Il est traité à la manière d'un triomphe à l'italienne, à la façon des longs cortèges du Quattrocento. Ce défilé unit les personnages de l'Ancien Testament à ceux du Nouveau et à tous les saints pour aboutir à la Parousie.
L'oeuvre des peintres italiens a malheureusement subi des transformations et de nombreuses restaurations qui pour l'essentiel ont été réalisées au cours du 19e siècle et la plupart du temps par des artistes de second ordre. La fabrique fait alors appel à deux peintres italiens : Jacques Bosia et Louis Guidi qui a beaucoup travaillé dans les chapelles situées au nord. En 1816, il restaure les parois de la chapelle 11 nord et refait les peintures de la voûte de la chapelle 14 nord. Vers 1818-1819, il peint le Christ au mont des Oliviers et le sépulcre gardé par des soldats dans la chapelle du Chris (10 nord). L'année suivante il repeint la voûte de la chapelle des deux saint Jean (2 nord) et remplace dans la chapelle saint Louis (9 nord) une inscription à la gloire de saint Georges par un verset de la prière liturgique pour les chefs d'état.
Dans les années 1820-1840, les peintures sont reprises dans d'autres chapelles du côté nord. La chapelle saint Michel et saint Martial (3 nord) est restaurée avant 1832 ; dans la chapelle de la Résurrection IM81001681 (5 nord), on peint une croix arborescente sur la paroi orientale pour effacer les traces de l'enlèvement de sculptures.
Sous le Second Empire les restaurations se poursuivent sous l'autorité de César Daly. Elles concernent les chapelles de l'abside et sont effectuées par le peintre décorateur parisien Alexandre Denuelle qui repeint les voûtes des 5 tribunes et reprend les chapelles des deux saints Jacques (3 sud) et de Pierre et Paul (2 sud). Dans cette dernière, il réalise la Pêche miraculeuse, la Conversion de saint Paul et le jugement des deux apôtres.
Joseph Engalières, artisan toulousain intervient dans les années 1870. Il repeint la chapelle du Christ (10 nord), restaure les chapelles voisines (11 et 12 nord). Dans la chapelle éponyme, il peint l'image du Sacré-Coeur et la voûte où il place les armes de Monseigneur Lyonnet (1865-1875), il repeint la chapelle du Rosaire (13 nord) et peint dans la chapelle suivante (14 nord) une frise et la figure de sainte Martiane sur le mur du fond.
La dernière campagne de restauration est entreprise autour de 1890. Marc Gaïda en est l'auteur. Il reprend au nord les chapelles 2, 3, 4, 5, 6 et 8 et travaille beaucoup au sud (chapelles 3, 5, 6, 7, 8, 9, 12 et 13). Il crée même un véritable décor à certains endroits, ajoutant des inscriptions dans la chapelle 8 nord et peignant une copie du Christ mort de Holbein dans la chapelle du saint Sépulcre.
