Ang lalawigan ng Nueva Vizcaya ay naging bahagi ng malawak na lambak ng Cagayan na dating iisang yunit pampolitika na pook na pinamumunuan ng isang gobernador. Noong 1839, ang noo'y gobernador heneral ng Pilipinas na si Luis Lardizabal, sa abiso ng noo'y alkalde mayor ng Cagayan, ay nagpalabas ng isang orden na lumikha sa Nueva Vizcaya bilang isang lalawigang politiko-militar. Pinagtibay ang nasabing orden sa isang Decreto Royal noong 10 Abril 1841.
Ang lalawigan ay nagkaroon ng unang pamamahalang sibil noong 1902 nang ito'y buuin ng Philippine Commission.
Mula nang maging lubos na at nagsasarili nang lalawigan ang Nueva Vizcaya, ang kasaysayan nito'y binubuo na ng kultura at tradisyon at paniniwala ng mga katutubong unang nanirahan dito na kinabibilangan ng mga Isinay, Gaddang, Bugkalot (o Ilongot), Igorot, Ifugao (Ipugaw), at nang lumaon ay ang mga Ilokano at iba pang pangkat etniko.