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 sont liées à la possession de reliques et à un pèlerinage à la Vierge au succès grandissant. L'évidente homogénéité de l'édifice dénote un chantier mené rapidement, c'est-à-dire entre le début du XIIe siècle et la date de la donation, 1166. Le clocher, dernier élément de la construction, date vraisemblablement, d'après son style, de la fin du XIIe siècle.
L'édifice est alors décoré : des portes ornées de pentures sont posées ;
vers 1170, une Vierge en majesté, à laquelle on prêtera plus tard un pouvoir thaumaturge, 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, endommagée à deux reprises au XVe siècle par des tremblements de terre, et la toiture, recouverte avant le XVIe siècle de tuiles qui ont été remplacées par des lauzes, à la suite d'un incendie. Le décor intérieur était, quant à lui, plus conséquent qu'aujourd'hui ; outre un badigeon (clair et ocre rouge?) sur les murs, les piles, les colonnes et les chapiteaux, vraisemblablement présent dès l'origine et dont il reste quelques traces, de nombreux ornements avaient été ajoutés, en particulier au XVIIe siècle : tapisseries habillant le rond-point du choeur, objets d'orfèvrerie, ex-voto, ... La plupart ont disparu à la Révolution.
Si cette période a vu également la suppression du chapitre, elle 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.
Les principaux projets de restauration de l'époque, et du XXe siècle, vont donc porter essentiellement sur une restitution supposée de l'état d'origine. Tous n'aboutiront pas.
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.
