Selama abad 16, para pelaut Spanyol melihat jalur yang lebih baik ke kepulauan Spice dengan melalui Papua. Pada 1529, Alvaro de Saavedra, seorang berkebangsaan spanyol, merupakan orang Eropa pertama yang datang menginjakkan kakinya di Papua. Selanjutnya para pelaut spanyol lainnya, Ynigo Ortiz de Retez, menetap cukup lama sehingga cukup untuk mengklaim bahwa Papua adalah masuk wilayah kekuasaan Spanyol dan menamakan pulau tersebut sebagai Nueva Gvince (New Guinea) setelah melihat fakta bahwa penduduk asli berkulit gelap seperti orang-orang afrika. Misi mereka kesini adalah untuk mencari emas namun mereka tidak menemukan apa-apa.
Kemudian mereka menuju Panama dan tidak pernah kembali lagi, tetapi nama yang diberikan untuk pulau yang mereka temukan tetap digunakan, dan hingga beberapa waktu lamanya bagian barat pulau tersebut mereka sebut dengan West New Guinea atau Netherlands New Guinea dimana sekarang ini sebagian dari pulau tersebut merupakan wilayah dari Negara Papua New Guinea. Segera setelah serbuan singkat bangsa spanyol, karena perdagangan rempah-rempah, bangsa portugis kembali membuat kolonisasi Timor, tetapi bukan pulau besar, yang mereka sebut sebagai Ilha Papoia.
Di awal abad 17, pelaut Belanda membuat percobaan sementara untuk menduduki pulau tetapi dipukul mundur oleh penduduk pribumi. Basis Eropa pertama adalah Inggris yang didirikan dengan benteng di bagian barat pulau pada tahun 1793 tetapi kemudian ditinggalkan setelah dua tahun, sebagai penghuni tetap harus membinasakan oleh penyebaran penyakit dan juga gangguan dari colonial lainnya.
Agar dapat tetap melakukan perdagangan dengan bagian sebelah barat pulau dan tetap penyelesaian disini, Belanda membuat sebuah rencana dengan sultan Tidore di Maluku Utara yang mengklaim kedaulatan diluar bagian sebelah utara wilayah mereka. Melalui undang-undang pemerintah belanda pada 1814 dan 1848, perjanjian ini diperluas untuk mencakup seluruh bagian barat pulau, sedangkan bagian lain telah diklaim sebagai milik Inggris dan Jerman dimana selanjutnya oleh inggris sendiri.
Belanda telah eksis dan memperkuat basis di jawa dan bagian-bagian lain dari Indonesia, dengan membangun kekuatan di West New Guinea melalui otoritas sultan tidore. Memasuki akhir abad 19, Belanda bertujuan untuk memisahkan West New Guinea dari Kekuasaan Sultan Tidore dan melakukan kontrol langsung terhadap Papua.
Pada 1905, belanda mengambil alih klaim sultan atas wilayah barat West New Guinea melalui konpensasi pembayaran, dan membuat keseimbangan posisi yang sama dengan bagian sebelah utara. Upaya ini menimbulkan kontroversi di kalangan internal pemerintah belanda saat bertemu dengan kekuatan perlawanan.
Meskipun demikian pada 1909, pemerintah Hindia Belanda dengan sultan menandatangani bahwa di wilayah bagian timur kepulauan Indonesia, termasuk Tidore, sebuah perjanjian yang memberikan belanda untuk mengambil kontrol langsung mereka dalam hal ini wilayah pemerintahan sendiri sewaktu-waktu.
Menurut beberapa analisa, jauh sebelum itu, sesunggunya telah ada pengakuan internasional yang efektif bahwa West New Guinea merupakan bagian dan paket dari Hindia-Belanda Timur (Netherlands East Indies).
Pada beberapa waktu yang singkat, selama perang Napoleon pada awal abad 19, Belanda menghasilkan East Indies untuk memperkuat tentara Inggris. Ketika perang berakhir, Inggris mengembalikan koloni yang mereka dapat dari Belanda sesuai dengan London Agreement (1814-1824). Khususnya disebutkan didalam perjanjian dimana bagian sebelah timur pulau dari Netherlands East Indies, termasuk Netherlands New Guinea.
Karena itu dibuat perjanjian perbatasan antara British New Guinea dan Netherlands New Guinea. Perbatasan ini menegaskan kembali konfirmasi surat parlemen Inggris pada juli 1886, terutama mengenai “Correspondence respecting New Guinea” yang memberikan perhatian khusus pada perbatasan.
Sebagai koloni Belanda sejak awal abad 19 hingga menjelang pertengahan abad 20, Papua belum pernah dieksploitasi dan sebagian besar wilayahnya hanya dijadikan sebagai pusat dimana belanda dapat mengkontrol jalur laut dari perdagangan rempah-rempah.
Papua juga merupakan tempat pembuangan atau pengasingan para pembangkang dari Indonesia yang tidak sepaham dengan otoritas Belanda. Sebagai tempat pembuangan untuk perorangan yang menentang Belanda, Papua memiliki peran didalam perjuangan Indonesia untuk merebut kemerdekaan diawal abad 20.
Di akhit tahun 1920, sebanyak 823 orang Indonesia bersama-sama dengan anak dan istrinya, 473 orang, dikucilkan dan mencoba tinggal di Tanah Merah, sekitar 500 kilometer ke arah hulu Sungai Digul di Papua. Mereka adalah orang-orang yang dituduh terlibat membangkitkan semangat anti-kolonial di berbagai bagian di Indonesia.
Tanah Merah tidak dibersihkan dari infeksi nyamuk di tengah hutan, dimana untuk mencapai daerah tersebut diperlukan waktu tiga hari dengan menggunakan motor-boat dari muara sungai di pantai utara. Ini merupakan tempat mengerikan yang saat itu menjadi tempat tinggal sementara bagi para pemimpin bangsa Indonesia seperti Sutan Syahrir dan Mohammad Hatta. Selama mereka ditempatkan di Tanah Merah, Hatta, sebagai salah seorang pendiri Republik Indonesia, menulis buku “Alam Fikiran Yunani” (The World of Greek Thoughts), yang merupakan risalah mengenai perdamaian dan demokrasi.
Pengasingan para pejuang Indonesia di Digul dan menghabiskan waktu di Digul atau sebagai ex-Digul, merupakan lambang penghargaan diantara lingkaran pejuang di Indonesia. Karena itu, Digul memperkuat rasa kekeluargaan diantara orang Papua dengan orang-orang dari berbagai propinsi di Indonesia.