Il·lustració de la cova, obra de Martín Rico, publicada el 1857 en El Museo Universal .

L'origen de la cova com a lloc de culte és controvertit. La tradició afirma que Pelagi I, perseguint a un malfactor que s'hauria refugiat en aquesta gruta, es va trobar amb un ermità que donava culte a la Mare de Déu. L'ermità va pregar a Pelagi que perdonés al malfactor, ja que s'havia acollit a la protecció de la Mare de Déu, i li va dir que arribaria el dia en què ell també tindria necessitat de buscar empara a la Cova. Alguns historiadors diuen que el més versemblant és que Pelagio i els cristians, refugiats a la Cova dels musulmans, portessin alguna imatge de la Verge i la deixessin allí després de la seva victòria en la Batalla de Covadonga.

Les cròniques musulmanes sobre la Batalla de Covadonga diuen que en aquesta Cova es van refugiar les forces de Pelagi, alimentant-se de la mel deixada per les abelles en les esquerdes de la roca. Les cròniques cristianes afirmen que la intervenció miraculosa de la Mare de Déu va ser decisiva en la victòria, en repel·lir els atacs contra la Cova.

La primera construcció a la Santa Cova data de temps de Alfons I d'Astúries qui, per commemorar la victòria de Pelagi davant els musulmans, va manar construir una capella dedicada a la Mare de Déu, que donaria origen a l'advocació de la Mare de Déu de Covadonga (coneguda popularment com la Santina). A més de l'altar a la Verge se'n construir dos més de Sant Joan Baptista i Sant Andreu. Alfons I va fer lliurament d'aquesta església als monjos benedictins.

La cova estava recoberta de fusta però el 1777 un incendi va destruir la talla original de la Santina. L'actual talla data del segle xviii i va ser donada al Santuari per la Catedral de San Salvador d'Oviedo el 1778. La talla de la Verge és de fusta policromada, de dolces faccions, i sosté al Nen i una rosa d'or.

Durant la guerra civil la imatge de la Mare de Déu va desaparèixer, i va ser trobada a l'ambaixada d'Espanya a França el 1939. La capella actual, una recreació historicista d'estil neoromànic, és obra de l'arquitecte Luis Menéndez-Pidal i Álvarez.