Arkeologi menunjukkan bahawa Cagayan telah didiami selama setengah juta tahun, walaupun tiada jenazah manusia dari zaman dahulu lagi. Penduduk terawal adalah Agta, atau Atta, pengumpul makanan yang berkeliaran di hutan tanpa tempat tinggal yang tetap. Sebilangan besar tanah baru-baru ini telah dikembalikan kepada mereka.[petikan diperlukan] Sebahagian besar penduduk berasal dari Melayu. Berabad-abad sebelum kedatangan orang Sepanyol, penduduknya berdagang dengan orang India, Melayu, Cina, dan Jepun. Pada abad kesembilan belas kemakmuran yang ditemui dalam penanaman tembakau menyebabkan ramai orang Ilokano menetap di sini. Tembakau masih menjadi faktor utama dalam ekonomi Cagayan, walaupun zon ekonomi khas dan pelabuhan bebas telah diwujudkan untuk mengukuhkan dan mempelbagaikan ekonomi wilayah.

Semasa zaman Sepanyol, Lembah Cagayan mempunyai wilayah yang lebih besar daripada apa yang ada hari ini. Ia termasuk wilayah-wilayah wilayah yang disebutkan di atas dan bahagian timur wilayah Cordillera di Apayao, Kalinga, Ifugao dan Benguet. Ahli sejarah dan dakwah Jose Burgues, berkata, "Lembah Cagayan lama terdiri daripada wilayah Cagayan, Isabela dan Nueva Vizcaya serta Daerah tentera Apayao, Itaves, Quiangan, Cayapa dan Bintangan, ditambah dengan kawasan Sierra Madre untuk Lautan Pasifik dalam trajektori tersebut."[3]

Semasa Perang Dunia II di Balete Pass di Nueva Vizcaya, Jepun yang berundur di bawah Jeneral Tomoyuki Yamashita menggali dan bertahan selama tiga bulan terhadap pasukan Amerika dan Filipina yang akhirnya menghalau mereka; lulus kini dipanggil Dalton Pass sebagai penghormatan kepada Jenderal Dalton, AS, yang terbunuh dalam pertempuran.