Fra begynnelsen av den muslimske invasjonen av Hispania, hadde flyktninger og stridende fra den sørlige delen av halvøya beveget seg nordover for å unngå islamsk autoritet.Noen hadde søkt tilflukt i de avsidesliggende fjellene i Asturias i den nordvestlige delen av den iberiske halvøy.Der, blant de bortførte i sør, rekrutterte Pelagius sin gruppe krigere.Pelagius sine første handlinger var å nekte å betale jizya (skatt på ikke-muslimer) til muslimene lenger og å angripe de små umayyadiske garnisonene som hadde vært stasjonert i området.Til slutt klarte han å utvise en provinsguvernør ved navn Munuza fra Asturias.Han holdt territoriet mot en rekke forsøk på å gjenopprette muslimsk kontroll, og grunnla snart kongeriket Asturias, som ble en kristen høyborg mot ytterligere muslimsk ekspansjon.I de første årene utgjorde dette opprøret ingen trussel for de nye mestrene i Hispania, hvis maktsete var etablert i Córdoba.Pelagius var ikke alltid i stand til å holde muslimene utenfor Asturias, men de kunne heller ikke beseire ham, og så snart maurerne dro, ville han alltid gjenopprette kontrollen.Islamske styrker var fokusert på å raidere Narbonne og Gallia, og det var mangel på arbeidskraft for å slå ned et uvesentlig opprør i fjellene.Det var et Umayyad-nederlag i slaget ved Toulouse som sannsynligvis satte scenen for slaget ved Covadonga.Dette var det første alvorlige tilbakeslaget i den muslimske kampanjen i Sørvest-Europa.Motvillige til å returnere til Córdoba med slike ulegerte dårlige nyheter, bestemte Ummayad wāli, Anbasa ibn Suhaym Al-Kalbi, at å slå ned opprøret i Asturias på vei hjem ville gi troppene hans en enkel seier og heve deres flaggsmoral.Slaget resulterte i en seier for styrkene til Pelagius.Det blir tradisjonelt sett på som den grunnleggende begivenheten til kongeriket Asturias og dermed det første punktet for den kristne Reconquista.