Pelaut seperti Jan Carstenszoon pada abad ke-17 telah mencatat adanya pegunungan tinggi yang tertutup salju di tengah pulau Papua padahal letaknya di khatulistiwa. Bangsa Eropa menyebut kawasan ini dengan terra incognita yang berarti daerah yang belum terpetakan. Ekspedisi yang dipimpin Hendrikus Albertus Lorentz pada tahun 1909, berhasil melakukan kontak dengan suku di pedalaman Provinsi Papua Pegunungan, ekspedisi ini saat itu sedang mencari jalur mencapai Puncak Wilhelmina (sekarang disebut Puncak Trikora) yang terjal dan tertutup salju. Anggota ekspedisi tersebut beristirahat dan melihat prosesi adat di perkampungan suku Pesechem atau Pesegem (Nduga). Namanya kemudian diabadikan dalam nama Taman Nasional Lorentz. Setelah ekspedisi tersebut, dilakukan banyak ekspedisi lain oleh de Bruyn, Franssen Herderschee, Karel Doorman, dan lain-lain.

Ekspedisi oleh van Overeem dan Kremer tahun 1920 berhasil menemukan Lembah Swart (sekarang Lembah Toli di wilayah Tolikara) beserta suku Lani yang tinggal disana. Ekspedisi ini kemudian menemukan Danau Habema dan berhasil mencapai Puncak Wilhelmina dari sisi utara. Lembah Baliem yang dihuni suku Dani ditemukan secara tidak sengaja dari pesawat terbang oleh ekspedisi yang dipimpin Richard Archbold dari Museum Sejarah Alam Amerika di tahun 1938. Ekspedisi ini diperkuat oleh puluhan tentara Belanda beserta orang-orang Dayak sebagai pemikul barang. Bangsa Belanda menyebut Lembah Baliem dengan Groote Vallei atau "Lembah Besar".

Mitchel Zuckoff dalam bukunya Lost in Shangri-La tahun 2011 mengungkapkan, pada masa Perang Dunia II wilayah ini belum banyak dipetakan. Geografinya berupa pegunungan tinggi yang berawan dan hutan lebat ditambah suku pedalaman yang tidak familier banyak memakan korban. Salah satu insiden yang terkenal terjadi pada 13 Mei 1945 oleh pesawat Gremlin Special yang menabrak tepi gunung di Pass Valley, lebih tepatnya di Uwambo, Distrik Abenaho, Kabupaten Yalimo. Operasi khusus kemudian dikirimkan dan tiga orang berhasil diselamatkan. Kisah mereka bertahan hidup masuk berita di tahun itu.

Agama Kristen masuk ke Lembah Baliem tahun 1954 oleh tim misionaris dari Christian and Missionary Alliance (C&MA) Amerika yang diterbangkan dari Sentani. Anggotanya antara lain pendeta Lioyd Van Stone dan Einer Michelson. Tidak lama kemudian, Pemerintah Belanda melalui kontrolir Frits Veldkamp juga mendirikan pos pemerintahan disini untuk memperkuat pengaruhnya di pedalaman. Kemudian dibangunlah perkampungan, lapangan udara, dan sarana prasarana lain di wilayah ini yang menjadi cikal bakal Kota Wamena. Hari jadi Wamena diperingati tiap 10 Desember 1956 sesuai pendirian pos pemerintahan Belanda ini.[8][13]

Sterrengebergte atau Pegunungan Bintang yang terletak di ujung timur dekat perbatasan negara adalah salah satu wilayah yang belum dijelajahi Belanda. Perkumpulan Geografi Kerajaan Belanda atau KNAG (Koninklijk Nederlands Aardrijkskundig Genootschap) kemudian meluncurkan ekspedisi besar-besaran di tahun 1959 dengan membawa ilmuwan dari berbagai bidang seperti zoologi, botani, dan antropologi. Selain mendapatkan berbagai pengetahuan baru mengenai keadaan wilayah dan penduduknya, anggota ekspedisi juga berhasil menaiki Puncak Juliana (sekarang disebut Puncak Mandala). Sebelum memulai ekspedisi besar ini, dilakukan survei terlebih dahulu untuk mencari tempat yang cocok dijadikan kamp dan lapangan terbang. Pegawai Belanda seperti Jan Sneep, Nol Hermans, dan Pim Schoorl dikirim dalam ekspedisi kecil menuju Lembah Sibil di tahun 1955 dan bertemu penduduknya yaitu suku Sibil atau Ngalum. Tahun 1958, Pemerintah Belanda meresmikan pos pemerintahan di Lembah Sibil yang nantinya akan menjadi Kota Oksibil ibu kota Kabupaten Pegunungan Bintang. Pemerintahan Belanda di wilayah ini cukup singkat dengan masuknya wilayah Nugini Belanda ke Indonesia di tahun 1963.[14][15]

Setelah UU No. 16 Tahun 2022 diresmikan, para bupati di provinsi baru ini bekerjasama dengan Kementerian Dalam Negeri melalui Kelompok Kerja (Pokja) III Satgas Pengawalan Daerah Otonomi Baru untuk menyusun hal-hal yang perlu dipersiapkan supaya provinsi baru ini dapat segera berjalan seperti lokasi kantor gubernur dan dinas sementara, anggaran sementara sebelum diadakannya Pilkada, Aparatur Sipil Negara (ASN), serta dana hibah dari masing-masing kabupaten, provinsi induk, dan pemerintah pusat.[29] Pokja juga meninjau calon lokasi pusat perkantoran Pemerintah Provinsi kedepannya dengan alternatif yang ditawarkan antara Distrik Muliama, Wamena Kota, Megapura, atau Hubikiak. Sedangkan untuk kantor gubernur sementara berada di Kantor Dinas Pendidikan Kabupaten Jayawijaya walaupun ada rekomendasi lain seperti Mall Wamena. Plang nama kantor gubernur sementara terpasang di tanggal 6 September 2022 namun dirusak sehari kemudian oleh 9 anggota Himpunan Mahasiswa Kabupaten Jayawijaya (HMKJ) yang akhirnya ditangkap oleh kepolisian.[30][31][32] Tanggal 11 November 2022, Provinsi Papua Pegunungan beserta dua provinsi baru lainnya diresmikan oleh Menteri Dalam Negeri. Pada hari itu juga, mantan Kepala Kejaksaan Tinggi Papua Nikolaus Kondomo dilantik sebagai penjabat gubernur Papua Pegunungan.