Pohjois-Hispaniassa yhdeksännen vuosisadan lopulla Mozarabien kirjoittamien tekstien mukaan visigootit valitsivat vuonna 718 princepsikseen eli johtajakseen Pelagius-nimisen aatelismiehen (681-737). Pelagius, Asturian kuningaskunnan ensimmäinen hallitsija, oli Hispanian entisen kuninkaan Chindasuinthin pojanpoika ja Favilan poika, joka oli ollut visigoottien kuninkaan Egican (687-700) hovin arvohenkilö, perusti päämajan Cangas de Onísiin, Asturiaan, ja lietsoi kansannousua Umayyad-muslimeja vastaan.
Hispanian muslimien hyökkäyksen alusta lähtien niemimaan eteläosan pakolaiset ja taistelijat olivat siirtyneet pohjoiseen välttääkseen islamilaista valtaa. Jotkut olivat hakeutuneet turvapaikkaan Iberian niemimaan luoteisosassa sijaitsevaan Asturian syrjäiseen vuoristoon. Siellä Pelagius rekrytoi etelän riistettyjen joukosta taistelijajoukkonsa.
Historioitsija Joseph F. O’Callaghan sanoo, että Hispanian goottilaisen aristokratian jäänteillä oli yhä tärkeä rooli Hispanian yhteiskunnassa. Visigoottien vallan loppuvaiheessa Hispano-roomalaisten ja visigoottien assimiloituminen tapahtui kiihtyvällä vauhdilla. Heidän aatelistonsa oli alkanut ajatella muodostavansa yhden kansan, gens Gothorum tai Hispani. Tuntematon määrä heistä pakeni ja hakeutui Asturiaan tai Septimaniaan. Asturiassa he tukivat Pelagiuksen kapinaa ja muodostivat yhdessä alkuperäisväestön johtajien kanssa uuden aristokratian. Vuoristoalueen väestö koostui syntyperäisistä asturialaisista, galicialaisista, cantabrilaisista, baskilaisista ja muista Hispano-gotiikan yhteiskuntaan sulautumattomista ryhmistä.
Pelagiuksen ensimmäiset teot olivat kieltäytyminen maksamasta enää jizya-veroa (vero ei-muslimeilta) muslimeille ja hyökkääminen alueelle sijoitettujen pienten umayyadien varuskuntia vastaan. Lopulta hän onnistui karkottamaan Munuza-nimisen maakunnan kuvernöörin Asturiasta. Hän piti alueen hallussaan useita yrityksiä vastaan palauttaa muslimien hallinta, ja pian hän perusti Asturian kuningaskunnan, josta tuli kristittyjen linnake muslimien tulevaa laajentumista vastaan.
Ensimmäisten vuosien ajan tämä kapina ei aiheuttanut uhkaa Hispanian uusille herroille, joiden vallanpaikka oli perustettu Córdobaan. Näin ollen reaktio oli vain vähäinen ja pinnallinen. Pelagius ei aina kyennyt pitämään muslimeja poissa Asturiasta, mutta he eivät myöskään kyenneet kukistamaan häntä, ja heti kun maurit olivat lähteneet, hän otti aina uudelleen vallan. Islamilaiset joukot keskittyivät Narbonnen ja Gallian ryöstöretkiin, ja miehistä oli pulaa merkityksettömän kapinan kukistamiseen vuoristossa. Pelagius ei koskaan yrittänyt pakottaa asiaa väkisin, ja todennäköisesti Covadongan taistelu sai alkunsa muualla tapahtuneesta umayyadien tappiosta. Heinäkuun 9. päivänä 721 muslimien joukko, joka oli ylittänyt Pyreneet ja hyökännyt frankkien kuningaskuntaan, kärsi tappion Toulousen taistelussa nykyisessä Ranskassa. Tämä oli ensimmäinen vakava takaisku muslimien kampanjassa Lounais-Euroopassa. Ummayadin wāli Anbasa ibn Suhaym Al-Kalbi, joka ei halunnut palata Córdobaan näin yksiselitteisten huonojen uutisten kanssa, päätti, että Asturian kapinan kukistaminen kotimatkalla antaisi hänen joukoilleen helpon voiton ja kohottaisi niiden horjuvaa moraalia.