La fondation du prieuré ou doyenné Sainte-Marie de Souillac remonterait à l'an 909, date à laquelle Géraud, comte et abbé d'Aurillac fit don de ses possessions de Souillac aux moines bénédictins de Saint-Pierre d'Aurillac. En 1253, un bourg s'était déjà constitué autour du prieuré et ses habitants avaient obtenu du doyen la concession d'une charte de coutumes. L'établissement monastique n'obtint le statut d'abbaye qu'à la fin du 15e siècle.
Les nombreux épisodes de destructions et de reconstruction qu'il eut à subir entre le 16e et le 18e siècle expliquent que le cloître médiéval ait disparu et la que les bâtiments conventuels aient été reconstruits en totalité après 1659. L'abbé Henry de La Mothe Houdancourt (1628-1684) effectua également d'importantes réparations à l'église. Elles touchèrent notamment la coupole de la croisée du transept, les couronnements, la tour-porche ainsi que les toitures. Une seconde campagne de restauration importante fut menée par les architectes Questel et Malo (1840-1845). Elle fut sévèrement critiquée par Viollet-le-Duc et Paul Gout. D'autres suivirent à la fin du 19e siècle et, plus récemment, entre 1933 et 1936, époque à laquelle l'architecte Poutaraud établit les couvertures de lauzes que l'on voit aujourd'hui sur les coupoles.
La datation de l'église médiévale est encore sujette à interrogation. A en juger par l'examen des maçonneries, la construction du 12e siècle, commencée par le chevet, s'est poursuivie en trois ou quatre phases majeures probablement assez rapprochées dans le temps jusqu'à la tour occidentale qui a été conservée d'un édifice primitif attribué au 11e siècle. Le maintien de cette tour primitive coïnciderait avec l'abandon du grand portail qui aurait dû terminer le chantier du 12e siècle.
Selon Henri Pradalier, les rapprochements stylistiques avec la sculpture du portail nord de Cahors impliqueraient de placer la réalisation du chevet de Souillac dans les années 1150 au plus tôt. Les éléments du portail inachevé, du fait de leur affinité avec la sculpture de Moissac, auraient été réalisés plus tôt, "dans les années 1140", mais n'auraient été mis en place qu'à l'extrême fin du 12e siècle ou au début du 13e siècle lors de la réalisation de l'élévation occidentale. Pour Evelyne Proust (2004, p. 181-182), la sculpture du chevet de Souillac participerait des dernières manifestations d'un style qui se serait développé entre 1140 et 1170 dans les églises du Bas Limousin. Les reliefs de Souillac, davantage que de Moissac, seraient à rapprocher du portail de Beaulieu (Corrèze) dont on pense aujourd'hui qu'il ne fut mis en place que dans les dernières décennies du 12e siècle (Pêcheur et Proust 2005, p. 93-94). Cette dernière estimation, qui placerait la construction de l'église dans le dernier tiers du 12e siècle, offre l'avantage de résoudre la contradiction qui résidait dans le fait d'attribuer au portail ouest une date plus ancienne que celle du chevet alors que l'analyse montre clairement que la construction de l'édifice fut menée d'est en ouest. Elle est confortée par ailleurs par les nombreuses affinités qui rapprochent Souillac des églises assez voisines de Saint-Amand-de-Coly et de Saint-Sauveur de Rocamadour, elles-mêmes tardives dans le 12e siècle.
Au 19e siècle, une première campagne de restauration est conduite par les architectes Charles Auguste Questel et Charles Hector Malo de 1839 à 1848 ; la deuxième campagne est réalisée par l'architecte Paul Gout de 1881 à 1895. Une troisième campagne de restauration, au cours de laquelle sont en particulier dégagées les coupoles de l'église qui reçoivent de nouvelles couvertures, est entreprise entre 1933 et 1936 par l'architecte en chef des Monuments historiques Poutaraud et l'inspecteur général Henri Nodet.
