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 Ibanag 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.