Eloigné des trajets des invasions, Orcival a probablement abrité des reliques de la Vierge venues de "Pont l'Abei" vers 878. La mention d'un prieuré de la Chaise-Dieu à Orcival, simple administration des terres que l'abbaye possédait en ce lieu, apparaît en 1166. En revanche, l'abbaye de la Chaise-Dieu n'est pas fondatrice de l'église, puisqu'elle en accepte la donation partielle en 1166 par le comte d'Auvergne, Guillaume VII, et son vassal Mathieu. L'édification est donc plus sûrement dûe aux comtes d'Auvergne associés au puissant évêque de Clermont, et peut-être aussi à quelques vassaux.

Les raisons de cette construction, entre le début du XIIe siècle et la date de la donation 1166, sont liées à la possession de reliques et à un pèlerinage à la Vierge au succès grandissant
Vers 1170, une Vierge en majesté, est réalisée. Pour donner plus de solennité au culte, un chapitre est érigé en 1245, sous le vocable de Notre-Dame.
Peu de transformations sont intervenues sur le bâtiment au cours des siècles. Les principales ont touché la flèche du clocher et la toiture d'origine en tuiles. Le décor intérieur était, quant à lui, plus conséquent qu'aujourd'hui : badigeon sur les murs, piles, colonnes et chapiteaux et nombreux ornements, ajoutés en particulier au XVIIe siècle. La plupart ont disparu à la Révolution.
Cette période a, en revanche, relativement épargné l'édifice lui-même. Ainsi, lors de l'émergence de la notion d'art roman, au XIXe siècle, cette église, considérée jusqu'alors comme "très ordinaire", va être regardée du point de vue de l'architecture et de l'histoire de l'art. Elle est classée comme monument historique en 1840.
En 1894, Notre-Dame d'Orcival est élevée au rang de basilique mineure. Après des travaux de restauration et la création d'un nouveau mobilier liturgique, elle est une nouvelle fois consacrée en 1958.