Sekitar Tahun 200 M, ahli Geography bernama Ptolamy menyebutnya dengan nama Labadios. Belum diketahui maksudnya apa disebut demikian. Di akhir tahun 500 M, pengarang Tiongkok bernama Ghau Yu Kua memberi nama Tungki, dan pada akhir tahun 600 M, Kerajaan Sriwijaya menyebut nama Papua dengan menggunakan nama Janggi.
Nama Tungki dan Janggi telah mengundang berbagai pendapat, kemungkinan nama Tungki yang sudah berubah dalam sebutannya menjadi Janggi atau sebaliknya. Pada akhir tahun 1300, Majapahit menggunakan dua nama, yakni Wanin dan Sram.
Nama Wanin, tentu tidak lain dari semenanjung Onin di daerah Fak-Fak dan Sram, ialah pulau Seram di Maluku. Ada kemungkinan, budak yang dibawa dan dipersembahkan kepada Majapahit berasal dari Onin, dan yang membawanya ke sana adalah orang Seram dari Maluku, sehingga dua nama ini disebut.
Tidore memberi nama untuk pulau ini dan penduduknya sebagai Papa-Ua yang sudah berubah dalam sebutan menjadi Papua. Pada tahun 1545, Inigo Ortiz de Retes memberi nama Nueva Guinee. Dan ada pelaut lain yang memberi nama Isla Del Oro, yang artinya Pulau Emas.
Nama Nueva Guinee kemudian di-Belanda-kan menjadi Nieuw Guinea. Pada tahun 1956, Belanda merubah nama Niew Guinea menjadi Nederlands Nieuw Guinea. Perubahan nama Nieuw Guinea menjadi Nederlands Nieuw Guinea mengandung maksud positive dan maksud negative.
Positivenya ialah karena nama Nieuw Guinea sering dihubungkan dengan sejarah Hindia Belanda (Nederlands Indie), terutama pihak Indonesia sering menggunakan ini sebagai alasan menuntut Nieuw Guinea dari Belanda.
Negativenya ialah bahwa sebelum Nieuw Guinea dijual, lebih dahulu dijadikan milik Belanda. Hal ini terbukti kemudian, bahwa Nederlands Nieuw Guinea bersama Nederlands Onderdaan yang hidup diatasnya, dijual kepada Indonesia pada 1962. Belanda merasa berhak berbuat demikian, karena sejak 1956, West Papua telah dijadikan miliknya.
Apa yang dilakukan Pemerintah Belanda dimasa itu, paralel dengan tindakan Synode Gereja Hervormd Belanda, sebab pada tahun 1956 itu juga, melepaskan tanggung-jawabnya kepada Dewan Gereja-Gereja di Indonesia.
Pada tahun 1961, Komite Nasional Papua yang pertama menetapkan nama Papua Barat. Pada masa Pemerintahan Sementera PBB (UNTEA), menggunakan dua nama, West New Guinea/West Irian.
Pada tanggal 1 Mei 1963, Irian Barat pun resmi menjadi wilayah Republik Indonesia berdasarakan Persetujuan New York yang ditandatangani 15 Agustus 1962. Republik Indonesia masih menggunakan nama Irian Barat.
Namun, Bung Karno sudah mempersiapkan nama kala itu, yang di dapatnya dari salah seorang pejuang tanah air, nama itu ialah Irian Jaya, yang berarti Ikut Republik Indonesia Anti Nedherland dan kata Jaya artinya menang.
Setelah Proklamasi kemerdekaan tanggal 1 Juli 1971, Pemerintah Revolusioner sementara Republik West Papua di Markas Victoria, menggunakan nama West Papua.
Pada tahun 1973, Pemerintah Republik Indonesia di West Papua merubah nama Irian Barat menjadi Irian Jaya.
Pada tahun 2000 nama Irian Jaya kembali menjadi Papua hingga kini.
Nama Papua, aslinya Papa-Ua, asal dari bahasa Maluku Utara. Maksud sebenarnya, bahwa di pulau ini tidak terdapat seorang raja, yang memerintah disini sebagai seorang bapak, itulah sebabnya pulau dan penduduknya disebut demikian.
Papa-Ua artinya anak piatu. Dari sekian nama yang sudah disebut, Komite Nasional Papua pada tahun 1961, memilih dan menetapkan nama PAPUA, karena rakyat disini kelak disebut bangsa Papua dan tanah airnya Papua Barat (West Papua).
Alasan memilih nama Papua, karena sesuai dengan kenyataan, bahwa penduduk pulau Papua sejak nenek moyang tidak terdapat dinasti yang memerintah atau raja disini, sebagaimana yang ada dibagian bumi yang lain. Orang Papua berdiri sama tinggi dan duduk sama rendah.
Tidak ada yang dipertuan untuk disembah dan tidak ada yang diperbudak untuk diperhamba. Raja-raja yang tumbuh seperti jamur di Indonesia, adalah akibat pengaruh pedagang bangsa Hindu dan Arab dimasa lampau.
Inilah sebabnya maka rakyat Papua anti kolonialisme, imperialisme, dan neo-kolonialisme. Nenek moyang mereka tidak pernah menyembah-nyembah kepada orang lain, baik dalam lingkungan sendiri. Mereka lahir dan tumbuh diatas tanah airnya sendiri sebagai orang merdeka.
Nama Irian adalah satu nama yang mengandung arti politik. Frans Kaisiepo, almahrum, orang yang pertama mengumumkan nama ini pada konperensi di Malino, Ujung Pandang pada tahun 1945, antara lain berkata : “Perubahan nama Papua menjadi Irian, kecuali mempunyai arti historis, juga mengandung semangat perjuangan : IRIAN artinya Ikut Republik Indonesia Anti Nederland”. (Buku PEPERA 1969 terbitan tahun 1972, hal. 107-108).
Nama Irian diciptakan oleh seorang Indonesia asal Jawa bernama Soegoro, bekas buangan Digul-Atas, tetapi dibebaskan sehabis Perang Dunia kedua dan pernah menjabat Direktur Sekolah Pendidikan administrasi pemerintahan di Hollandia antara tahun 1945-1946.
Perubahan nama Irian Barat menjadi Irian Jaya, terjadi pada tahun 1973, juga mengandung arti politik. Regiem Militer Indonesia tidak menginginkan adanya pembagian Pulau Papua menjadi dua dan berambisi guna menguasai seluruhnya.
Pendirian ini berdasarkan pengalaman tentang adanya dua Vietnam-Selatan dan Utara, tentang adanya dua Jerman-Barat dan Timur, dan tentang adanya dua Korea-Selatan dan Utara. Irian Jaya, Irian yang dimenangkan. Jaya, victoria atau kemenangan. Jika huruf “Y” dipotong kakinya, maka akan terbaca Irian Java alias Irian Jawa.