Από την αρχή της μουσουλμανικής εισβολής στην Ισπανία, πρόσφυγες και μαχητές από τα νότια της χερσονήσου είχαν μετακινηθεί βόρεια για να αποφύγουν την ισλαμική εξουσία.Μερικοί είχαν καταφύγει στα απομακρυσμένα βουνά της Αστούριας στο βορειοδυτικό τμήμα της Ιβηρικής χερσονήσου.Εκεί, μεταξύ των αποστερημένων του νότου, ο Πελάγιος στρατολόγησε την ομάδα των μαχητών του.Οι πρώτες ενέργειες του Πελάγιου ήταν να αρνηθεί να πληρώσει πια τον τζίζια (φόρο για τους μη μουσουλμάνους) στους Μουσουλμάνους και να επιτεθεί στις μικρές φρουρές των Ομαγιάδων που είχαν σταθμεύσει στην περιοχή.Τελικά, κατάφερε να εκδιώξει έναν επαρχιακό κυβερνήτη που ονομαζόταν Munuza από την Asturias.Κράτησε την επικράτεια ενάντια σε μια σειρά προσπαθειών να αποκαταστήσει τον μουσουλμανικό έλεγχο και σύντομα ίδρυσε το Βασίλειο της Αστούριας, το οποίο έγινε χριστιανικό προπύργιο ενάντια στην περαιτέρω μουσουλμανική επέκταση.Για τα πρώτα χρόνια, αυτή η εξέγερση δεν αποτελούσε απειλή για τους νέους κυρίους της Ισπανίας, των οποίων η έδρα της εξουσίας είχε εγκατασταθεί στην Κόρδοβα.Ο Πελάγιος δεν ήταν πάντα σε θέση να κρατήσει τους Μουσουλμάνους έξω από την Αστούρια, αλλά ούτε και μπορούσαν να τον νικήσουν, και μόλις οι Μαυριτανοί έφευγαν, πάντα θα αποκαθιστούσε τον έλεγχο.Οι ισλαμικές δυνάμεις επικεντρώθηκαν στην επιδρομή της Ναρμπόνης και της Γαλατίας και υπήρχε έλλειψη ανθρώπινου δυναμικού για να καταστείλει μια ασήμαντη εξέγερση στα βουνά.Ήταν μια ήττα των Ομαγιάδων στη Μάχη της Τουλούζης που πιθανότατα έθεσε το υπόβαθρο για τη μάχη της Covadonga.Αυτή ήταν η πρώτη σοβαρή οπισθοδρόμηση στη μουσουλμανική εκστρατεία στη νοτιοδυτική Ευρώπη.Απρόθυμος να επιστρέψει στην Κόρδοβα με τέτοια ασυνήθιστα άσχημα νέα, ο Ουμμαγιάντ ουάλι, Anbasa ibn Suhaym Al-Kalbi, αποφάσισε ότι η καταστολή της εξέγερσης στην Αστούριας στο δρόμο για το σπίτι του θα επέτρεπε στα στρατεύματά του μια εύκολη νίκη και θα ανέβαζε το ηθικό τους.Η Μάχη κατέληξε σε νίκη των δυνάμεων του Πελαγίου.Θεωρείται παραδοσιακά ως το θεμελιώδες γεγονός του Βασιλείου της Αστούριας και ως εκ τούτου το αρχικό σημείο της Χριστιανικής Ρεκκονκίστας.