ARCHEOLOGICAL FINDINGS dating back to the Paleolithic Age indicate that the ancestors of modern humans had settled in Cagayan as early as 500,000 years ago. Man may have followed large mammals into the valley in search of game. The Agtas were probably the first modern humans to populate the vast Cagayan Valley region, followed by various Malayo-Polynesian groups who settled in the Cagayan plains and established culturally similar but ethically distinct communities.

Spanish explorer Juan de Salcedo explored the coast of Cagayan in 1572 and found the people conducting trade with Chinese and Japanese merchants. In 1582, after driving away Japanese pirates who had settled along the Cagayan coast, the Spaniards decided to settle in Lallo, which they renamed Nueva Segovia. In 1595, Nueva Segovia became the seat of a diocese, which covered the entire northern Luzon.

The pacification and settlement of the Cagayan proceeded slowly because of the hostility of the natives who were indisposed to colonization. Christian evangelization began in 1596 with the arrival of Dominican missionaries in Cagayan. Revolts continued to rock the province and threatened to supplant the Spanish colonial government in the area. These revolts found a continuing reservoir of support from the unconverted highland peoples who continually harassed the Christian settlement of the valley.

In the late 18th century, Cagayan felt the full impact of the tobacco monopoly. Cultivation of tobacco, which was an important article of trade and consumption, was initially prohibited. Anti-monopoly revolts broke out in 1787 and many settlements near the highlands were abandoned by natives who wanted to continue cultivating tobacco. Ten years later, tobacco cultivation was allowed in the valley and Cagayan soon became the single largest source of the cash crop in the archipelago. Ilokano migration into the valley facilitated the expansion of agriculture in the region. By the middle of the 19th century, the great number of Ilokano settlers allowed the Iloko language to supplant Ybanag as the regional lingua franca.

Under the Spaniards, the whole northeastern part of the island of Luzon, plus some small islands in the Balintang Channel constituted a single province of Cagayan. In 1839 the southern half of the valley was formed into a politico-military district of Nueva Vizcaya. In 1856, parts of Cagayan and Nueva Vizcaya were formed into the province of Isabela. Cagayan lost more territory with the formation of the partido of Itawes in 1889 and the comandancia of Apayao in 1890. The Americans delineated the present day limits of Cagayan in 1908.

In 1901, the United States Philippine Commission enacted Act No. 209 which in effect established the Provincial Government of Cagayan. In 1917, as contained in Act No. 2711, Cagayan was recognized as a grand division of the Philippine Islands. The province then comprised of 24 municipalities with Tuguegarao as its capital town.

During the Second World War, Japanese units landed in Aparri town a few days after the bombing of Pearl Harbor in December 1941. The valley again figured prominently in the plans of Japanese forces to defend it as a secure line of retreat to Taiwan in 1945. Filipino guerillas and American forces from Ilocos formally drove the Japanese to the Cordilleras.