Pada tahun 722, pasukan tentera yang diketuai oleh komander Umayyah, Al Qama dan Munuza, dan (mengikut lagenda) ditemani oleh Bishop Oppas[4] dari Seville, telah dihantar ke Asturias. Sebaik Al Qama menduduki wilayah ini, penglipur lara[5] menyatakan bahawa Oppas cuba menjadi pengantara bagi penyerahan sekutu Kristian beliau, akan tetapi menemui kegagalan. Pelagius dan tentera beliau berundur jauh ke kawasan pergunungan Asturias, hingga tiba ke sebuah lembah sempit yang diapit oleh gunung-gunung, yang mana senang dipertahankan di sebabkan kedudukannya yang mustahil untuk melakukan serangan luas dari arah hadapan. Pelagius mungkin memiliki beberapa ratus orang bersama beliau.

Al Qama akhirnya tiba di Covadonga, dan menghantar utusan untuk menpengaruhi Pelagius untuk menyerah diri. Beliau enggan, oleh itu Al Qama memerintahkan pasukan terbaik beliau untuk menyerbu lembah ini. Pasukan Asturian menyerang dari sisi gunung, dan kemudian semasa kemuncak pertempuran, Pelagius telah mengetuai tentera beliau masuk ke dalam lembah. Mereka bersembunyi di dalam sebuah gua yang tidak dapat dilihat oleh pasukan Muslim. Kisah dari pihak Kristian menyebut penyembelihan menakutkan ke atas tentera Muslim, sementara sejarah Umayyah menyebut ia hanya sebagai serangan kecil. Al Qama terbunuh di dalam pertempuran ini manakala tentera beliau pula telah melarikan diri daripada medan pertempuran.

Selepas kemenangan Pelagius, penduduk di Asturias mengambil senjata dan mula membunuh beratus-ratus orang tentera Al Qama yang melarikan diri. Munuza, yang mendapat tahu akan kekalahan ini, menyusun pasukan tentera baru dan mengumpul sisa-sisa yang terselamat dari Covadonga. Tidak lama kemudiann, beliau bertemu dengan Pelagius berdekatan dengan bandar Proaza (kini). Sekali lagi kemengan berpihak kepada Pelagius, dan Munuza terbunuh di dalam pertempuran. Meskipun Muslim memanggil Pelagius dan tentera beliau sebagai "30 orang kafir yang tinggal, apa yang mereka boleh buat", mereka tidak pernah lagi menentang secara serius kemerdekaan Kerajaan beraja Asturias.