Berdasarkan kepada teks yang ditulis oleh Mozarabs di utara Iberia dalam kurun ke-9, pada tahun 718 puak Visigoths telah memilih seorang bangsawan yang bernama Pelagius (681-737) sebagai pemimpin mereka. Pelagius merupakan cucu kepada bekas Raja Hispania, Chindasuinth, dan anak lelaki kepada Favila, yang mana merupakan seorang bangsawan di istana Raja Visigoth Egica (687-700). Beliau telah membina ibu kota di Cangas de Onís, Asturias dan memulakan penentangan terhadap pemerintahan khilafah Islam Umayyah.

Sejak permulaan kempen penaklukan Islam ke atas Iberia, pelarian dan tentera daripada bahagian selatan semenanjung melarikan diri ke bahagian utara untuk mengelak dari pemerintahan Islam. Antara mereka bersembunyi di kawasan pergunungan terpencil Asturias yang terletak di barat laut semenanjung Iberia. Mereka ini kemudian direkrut dan diserap oleh Pelagius ke dalam pasukan tenteranya. Tindakan pertama beliau adalah enggan membayar Jizya (cukai ke atas bukan Islam) kepada pemerintah Islam dan mula menyerang perbatasan kecil yang diletakkan di kawasan ini. Akhirnya, beliau berjaya menghalau gabenor daerah yang bernama Munuza dari Asturias. Beliau berjaya memegang wilayah ini daripada beberapa percubaan yang dilakukan khilafah Islam untuk menawan semula, dan tidak berapa kemudian menubuhkan Kerajaan beraja Asturias, yang mana menjadi kubu kuat Kristian untuk menentang usaha perluasan wilayah oleh Muslim.

Bagi 50 tahun pertama, pemberontakkan ini tidak mendatangkan ancaman kepada khilafah Islam Umayyah di Hispania, yang mana berpusat di Cordoba. Pelagius tidak sepenuhnya berjaya menghalau keluar Muslim daripada Asturias atau mengalahkan mereka, sebaik sahaja pasukan tentera Islam meninggalkan wilayah ini, beliau berjaya mengambil alih kawalan semula. Pasukan tentera Islam mengfokuskan akan serangan ke atas Narbonne dan Gaul, dan menghadapi masalah kekurangan tenaga untuk mengawal wilayah pergunungan ini. Pelagius tidak pernah cuba menekan isu ini. Kekalahan Umayyah di tempat lain membuka peluang kemenangan dalam Petempuran Covadonga. Pada 9 Julai, 721, sebuah pasukan Muslim yang menyeberangi Pyrenees dan menyerang kerajaan beraja Franks telah dikalahkan dalam Pertempuran Toulouse, kini terletak di Perancis. Kejadian merupakan kekalahan serius pertama dalam kempen Muslim di barat daya Eropah. Enggan kembali ke Cordoba dengan berita buruk ini, wāli Umayyah, Anbasa ibn Suhaym Al-Kalbi, memutuskan untuk menghancurkan pemberontakkan di Asturias semasa dalam perjalanan pulang bagi mendapatkan kemenangan mudah dan menaikan moral tentera beliau.