Apayao was among the earliest areas penetrated by the Spaniards in the Cordilleras, but the region, inhabited by the Isneg tribe, remained largely outside Spanish control until late in the 1800s. As early as 1610, the Dominican friars established a mission in what is now the town of Pudtol. In 1684, the friars again made vain attempts to convert the people and established a church in what is now Cabugao. The ruins of the early churches in Pudtol and Cabugao still stand as mute testimony to the failed attempts to occupy Apayao.

The Spanish authorities were then able to establish the comandancias of Apayao and Cabugaoan in 1891, which covered the western and eastern portions of what is now Apayao. The comandancias, however, failed to bring total control and the Spanish government only maintained a loose hold over the area.

The Americans established the Mountain Province on August 13, 1908, In 1942, it was occupied by the Japanese Imperial forces.

In 1945, the liberation of Apayao by the Philippine Commonwealth Army troops and the military forces of USAFIP-NL was supported by the local Cordilleran guerrilla fighters against the Japanese Imperial forces during the Battle of Apayao until the end in World War II.

After being a sub-province for almost 60 years, on June 18, 1966, the huge Mountain Province was split into four. The four new provinces being Benguet, Mountain Province, Kalinga-Apayao and Ifugao. Kalinga-Apayao became one of the provinces of the Cagayan Valley region.

On July 15th 1987, the Cordillera Administrative Region was established and Kalinga-Apayao was made one of its provinces. Finally, on February 14th 1995, Kalinga-Apayao was split into two provinces each bearing it's own name.