From the beginning of the Muslim invasion of Hispania, refugees and combatants from the south of the peninsula had been moving north to avoid Islamic authority. Some had taken refuge in the remote mountains of Asturias in the northwestern part of the Iberian peninsula. There, from among the dispossessed of the south, Pelagius recruited his band of fighters.

Pelagius's first acts were to refuse to pay the jizya (tax on non-Muslims) to the Muslims any longer and to assault the small Umayyad garrisons that had been stationed in the area. Eventually, he managed to expel a provincial governor named Munuza from Asturias. He held the territory against a number of attempts to re-establish Muslim control, and soon founded the Kingdom of Asturias, which became a Christian stronghold against further Muslim expansion.

For the first few years, this rebellion posed no threat to the new masters of Hispania, whose seat of power had been established at Córdoba. Pelagius was not always able to keep the Muslims out of Asturias but neither could they defeat him, and as soon as the Moors left, he would always re-establish control. Islamic forces were focused on raiding Narbonne and Gaul, and there was a shortage of manpower for putting down an inconsequential insurrection in the mountains. It was an Umayyad defeat at the Battle of Toulouse that probably set the stage for the Battle of Covadonga. This was the first serious setback in the Muslim campaign in southwestern Europe. Reluctant to return to Córdoba with such unalloyed bad news, the Ummayad wāli, Anbasa ibn Suhaym Al-Kalbi, decided that putting down the rebellion in Asturias on his way home would afford his troops an easy victory and raise their flagging morale.

The Battle resulted in a victory for the forces of Pelagius. It is traditionally regarded as the foundational event of the Kingdom of Asturias and thus the initial point of the Christian Reconquista.