Fra begyndelsen af ​​den muslimske invasion af Hispania havde flygtninge og kombattanter fra den sydlige del af halvøen bevæget sig nordpå for at undgå islamisk autoritet.Nogle havde søgt tilflugt i de afsidesliggende bjerge i Asturien i den nordvestlige del af den iberiske halvø.Der, blandt de fordrevne i syd, rekrutterede Pelagius sin gruppe krigere.Pelagius' første handlinger var at nægte at betale jizya (skat på ikke-muslimer) til muslimerne længere og at angribe de små umayyadiske garnisoner, der havde været stationeret i området.Til sidst lykkedes det ham at udvise en provinsguvernør ved navn Munuza fra Asturien.Han holdt territoriet imod en række forsøg på at genetablere muslimsk kontrol og grundlagde snart Kongeriget Asturien, som blev en kristen højborg mod yderligere muslimsk ekspansion.I de første par år udgjorde dette oprør ingen trussel for de nye mestre i Hispania, hvis magtsæde var blevet etableret i Córdoba.Pelagius var ikke altid i stand til at holde muslimerne ude af Asturien, men de kunne heller ikke besejre ham, og så snart maurerne rejste, ville han altid genetablere kontrollen.Islamiske styrker var fokuseret på at angribe Narbonne og Gallien, og der var mangel på arbejdskraft til at nedlægge et uvæsentligt oprør i bjergene.Det var et umayyadisk nederlag i slaget ved Toulouse, der sandsynligvis satte scenen for slaget ved Covadonga.Dette var det første alvorlige tilbageslag i den muslimske kampagne i det sydvestlige Europa.Uvillige til at vende tilbage til Córdoba med sådanne ulegerede dårlige nyheder besluttede Ummayad wāli, Anbasa ibn Suhaym Al-Kalbi, at at slå oprøret i Asturien ned på vej hjem ville give hans tropper en let sejr og hæve deres flagrende moral.Slaget resulterede i en sejr for Pelagius styrker.Det betragtes traditionelt som den grundlæggende begivenhed for Kongeriget Asturien og dermed det indledende punkt i den kristne Reconquista.