Gugusan kepulauan Papua dan yang secara tradisional dimiliki oleh ras Melanisean terpecah-pecah menjadi kawasan yang dikuasai oleh penjajah. Pada tahun 1848 Belanda dan Inggris secara abstrak membagi kepulaun itu dalam garis bujur 141 derajat. Separuh di wilayah timur, yang kini dikenal sebagai Papua Nugini, dibagi dan dikuasai masing-masing oleh Inggris dan Jerman (1884). Bagian selatan, dikuasai oleh Inggris dan kemudian dikuasai oleh Australia (1906). Kawasan utara, awalnya dikuasai Jerman, tetapi setelah Perang Dunia I dimandatkan kepada Australia dan selanjutnya dikelola oleh Australia hingga Perang Dunia II, termasuk kawasan Papua Nugini. Pada tahun 1975, Australia memberikan kemerdekaan bagi Papua Nugini. Kemudian, di paruh lain kawasan selatan, dikuasai oleh Belanda, dikenal sebagai Papua Barat, yang tidak pernah memperoleh kemerdekaan. Dengan penguasaan Jepang yang berlangsung singkat selama Perang Dunia II, wilayah Papua diterlantarkan oleh Belanda. Tidak seperti dugaan awal para pedagang Asia yang menganggap Papua adalah tanah kaya, Belanda, dengan pemerintahan pusat di Batavia, justru menjadikan Papua sebagai tanah pembuangan aktivis politik dan sebagai strategi untuk mengendalikan jalur laut perdagangan rempah-rempah.
Pada tahun 1945, hanya dua hari setelah Jepang menyerah kepada Sekutu di akhir Perang Dunia II, sekelompok pejuang Indonesia menyatakan Proklamasi Kemerdekaan atas seluruh bekas wilayah Hindia Belanda. Sebagai upaya untuk menuntut kembali daerah jajahannya yang makmur, Belanda menolak untuk mengakui kemerdekaan tersebut dan salama 4 tahun berikutnya terjadi perjuangan mempertahankan kemerdekaan di republik yang masih muda tersebut. setelah memperoleh tekanan internasional, suatu persetujuan dicapai antara Indonesia dan Belanda dalam forum Konferensi Meja Bundar bahwa Belanda mengakui kemerdekaan pada 27 Desember 1949 dan Soekarno ditetapkan sebagai Presiden. Untuk memfasilitasi kesepakataan awal diantara dua pihak yang bersikukuh satu sama lain, persetujuan itu menetapkan bahwa wilayah Papua Barat tetap di bawah penguasaan Belanda dan dalam 1 tahun sesudahnya Belanda dan Indonesia akan menyelesaikan persoalan itu. Sampai awal tahun 1950-an, perundingan mengalami kebuntuan dan Belanda justru mempersiapkan hak menentukan nasib sendiri yang rencananya akan dilaksanakan pada tahun 1970. Di bawah kendali Belanda, berhasil dibentuk Dewan Perwakilan Rakyat Papu pada tahun 1961 melalui suatu pemilu. Partai politik dan serikat pekerja dibentuk, posisi pegawai negeri diisi oleh kalangan pribumi Papua, dan suatu rencana untuk menempatkan Papua di bawah pengawasan PBB dipublikasikan. Bahkan, puncaknya, bendera nasional dan lagu kebangsaan diperkenalkan dan kalangan Barat memberi nama baru untuk kawasan itu: Papua Barat.
Dengan peningkatan dekolonisasi Belanda di kawasan itu, Presiden Soekarno menjadi bersemangat perhatiannya terhadap Papua, yang mana dianggap sebagai bagian dari visinya mengenai Indonesia yang hendak menjangkau seluruh bekas wilayah Hindia Belanda, tetapi hal itu akan digagalkan oleh Belanda dengan penguasaan Papua. Sesudah negosiasi diplomatic dengan PBB dianggap tidak segera memperoleh hasil, Presiden Soekarno memutuskan untuk menggunakan kekuatan angkatan bersenjatra guna mencegah Papua Barat memperoleh kemerdekaan. Di bawah komando seorang perwira muda, Mayor Jenderal Soeharto (kelak Presiden Indonesia, 1966-1998), operasi militer dan kesatuan sukarelawan diterjunkan di Papua (1961). Ancaman perang telah di depan mata, guna mempertahankan klaim Papua sebagai wilayah Indonesia. Di bawah tekanan Amerika, dan dukungan lain secara penuh dari PBB, Belanda menyetujui kesepakatan dengan Indonesia yang disponsori PBB, yang dikenal sebagai New York Agreement (1963). Secara teoritis, dokumen ini mendukung hak menentukan sendiri bagi Papua. Di dalam praktik, dokumen ini memastikan kedaulatan Papua berada di posisi Indonesia. Seorang diplomat Inggris memberikan pendapatnya di tahun 1968 sebagai berikut:
Bagaimanapun, dapat dikatakan, tiada pihak lain yang begitu gigih untuk mengupayakan dengan sekuat tenaga supaya Papua menjadi wilayah Indonesia, dengan bantuan PBB, jika tidak ada sesuatu mengenai wilayah itu. Bahkan ada satu kemungkinan khusus yang dilupakan mengenai apakah Indonesia mempertahankan wilayah itu dengan baik atau dengan kekerasan dan siapakah yang bersikeras untuk memancing kemarahan 115 juta penduduk yang kemudian dijadikannya sebagai kawan…Kemerdekaan bagi hampir 800.000 penduduk sudah hampir digenggam…Secara alami orang akan bersimpati kepada penduduk pribumi tetapi kolonialisasi tidak selamanya sesuatu yang buruk.
Dengan kesepakatan New York itu maka Indonesia akan berkuasa sampai dilaksanakan referendum di tahun 1969 di bawah pengawasan PBB yang mana penduduk Papua dipersilakan apakah akan merdeka atau bergabung dengan Indonesia. PBB kemudian menempatkan aparaturnya guna memastikan peralihan dari Belanda ke Indonesia melalui suatu pemerintahan sementara, guna menjamin hak-hak penduduk Papua.
Pada tahun 1969 dilaksanakan referendum oleh Jakarta. Bertentangan dengan kesepakatan New York, Jakarta mengakui 1.024 orang, dengan pengawasan militer, mempunyai suara penuh untuk mewakili 1 juta penduduk Papua dan memutuskan bergabung dengan Indonesia. Sekalipun PBB menghendaki sistem “satu orang satu suara (one man, one vote) Jakarta menolak, dengan alasan ada kesulitan fisik untuk melaksanakan sistem itu dan “situasi” penduduk Papua belum memungkinkannya. Anehnya, tidak berapa lama kemudian, sistem itu dilaksanakan di Papu dalam pemilu (1971). Sesudah itu, nama Papua diganti oleh Orde Baru menjadi Irian Barat dan pada bulan Maret 1973, Soeharto mengubah lagi menjadi Irian Jaya.
Sebelum referendum itu dilaksanakan, pada tahun 1967 Jakarta mengizinkan melalui kontrak karya jangka panjang (30 tahun) kepada perusahaan tambang Amerika, Freeport. Dalam jangka pendek, kontrak itu dimaksudkan Orde Baru sebagai upaya untuk meraih dukungan politik dari Amerika dan mempertahankan keinginan untuk klaim Papua sebagai bagian wilayah Indonesia. Dan menurut Menteri Pertambangan saat itu, Soetaryo Sigit, “kontrak Freeport tersebut menyampaikan sinyal penting ke dunia internasional bahwa Indonesia menghormati penanaman modal asing.”
