L'église est située dans le département français de l'Aveyron, sur la commune de Bozouls, à l'intérieur du méandre appelé trou de Bozouls formé par le Dourdou.
Avec son abbaye-mère et plusieurs autres églises rattachées à cette abbaye, le prieuré est rattaché à l'abbaye Saint-Victor de Marseille avant 1082, probablement en 1079. Cette donation est confirmée par l'évêque de Marseille Adhémar, en 1120, mais dès 1140 le prieuré devient une possession du chapitre de la cathédrale de Rodez malgré l'opposition des moines de l'abbaye marseillaise. Une bulle du pape Alexandre III confirme en 1162 la possession du prieuré par le chapitre de la cathédrale de Rodez.
L'église a été construite au XIIe siècle, probablement pendant la période de possession de l'église par l'abbaye Saint-Victor à la place d'une église du XIe siècle dont il subsiste quelques éléments.
L'étage le plus haut du clocher date du XIVe siècle.
Cinq chapelles sont greffées sur le côté sud de l'église aux XVe et XVIe siècles. Ces constructions sont probablement à l'origine de l'écartement des piles en partie haute par défaut de stabilité. Cela a conduit à ajouter des arcs-boutants au XVIIe siècle. D'autres travaux seront faits pour alléger la toiture en remplaçant la lauze par l'ardoise. Les voûtes de la nef ont probablement dû être reconstruites à cette époque car leur position n'est pas compatible avec la corniche originelle dont les modillons sont visibles dans les combles des chapelles. Les contreforts du mur nord sont renforcés ainsi que le contrebutement du chevet au XVIIe siècle. Une tourelle d'escalier a été greffée sur le côté nord de la première travée. La chapelle haute du massif est divisée en deux par un mur.
En 1783, deux contreforts viennent renforcer la façade occidentale du clocher. Un avant-porche est ajouté en 1817 et la sacristie est construite en 1874-1875.
L'église est restaurée en 1946-1947 par un décrépissage de l'intérieur et une réfection des enduits, puis en 1970 ont lieu la réfection des charpentes et de la couverture. En 1980, les maçonneries dégradées sont reprises.
Laurence Cabrero-Ravel, Bozouls, église Sainte-Fauste, dans Congrès archéologique de France. 167e session. Monuments de l'Aveyron. 2009, Société française d'archéologie, Paris, 2011, p. 53-60
Jean-Claude Fau, Rouergue roman, Éditions Zodiaque, collection la Nuit des temps no 17, 3e édition, La Pierre-qui-Vire, 1991, (ISBN2-7369-0148-7), p. 273-318
Bernard de Gaulejac, Bozouls, p. 433-444, dans Congrès archéologique de France, 100e session, « Figeac, Cahors et Rodez », 1937, Société française d'archéologie, Paris, 1938, p. 570