Der Name Papua ist ursprünglich keine Selbstbezeichnung. Schon der Portugiese Jorge de Meneses, der die Nordwestküste 1526 erreichte, soll von den Inseln als den „Ilhas dos Papuas“ gesprochen haben. Er habe dabei das malaiische Wort „papuwah“ gebraucht, das „Menschen mit Kraushaar“ bezeichnen soll. In Tidore soll der Name Papua synonym mit „Sklave“ gebraucht worden sein. Der Sultan von Tidore erhielt seine Sklaven von den Ilhas dos Papuas. So bezeichnet das Wort ursprünglich die dunkelhäutigen Menschen, denen die portugiesischen und spanischen Seefahrer auf den Inseln am westlichen Rand des Pazifik begegneten. 1545 segelte der Spanier Ortiz di Retes an der Nordküste „Neuguineas“ entlang. Er gab dem Land diesen Namen, da ihn die Küste an das afrikanische Guinea erinnerte.
Der Name „Irian“ stammt wohl von dem Biakschen Wort „irjan“. Dies Wort bedeutet in Biak „schön, hell“, oder auch „aus dem Meer aufsteigend“. Bei den Menschen der Cendrawasih-Bucht bedeutet es „Land ohne Blutvergießen“ und in der Gegend von Numbai (Jayapura) bedeutet es „unser Eigentum“. Dies Wort wurde erstmals von dem Biaker Frans Kasiepo auf der Malino-Konferenz (1946, bei Makassar) zur Bezeichnung von West-Neuguinea gebraucht. Es wurde dann von proindonesischen Politikern aus West Papua und von der indonesischen Politik aufgegriffen und gebraucht.
1961 beschloss der Papuarat, im Gegensatz zum indonesischen Sprachgebrauch das Land „West-Papua“ zu nennen. Nach der Übernahme durch Indonesien wurde die offizielle Bezeichnung „Irian-Barat“ (West Irian), 1969 wurde die Provinz in „Irian-Jaya“ umbenannt. Die Bezeichnung Papua oder West-Papua wurde von den Indonesiern verboten. Der Name Irian Jaya war bei den Papua verhasst, deswegen forderten sie von 1998 an eine Umbenennung in Papua oder West Papua. Erst seit dem 1.1.2002 ist mit dem in Kraft treten des Sonderautonomiegesetzes der Name der Provinz nun offiziell Papua.
Am 27.1.2003 erließ die Präsidentin Megawati Sukarnoputri eine Verordnung zur Beschleunigung der Aufteilung Papuas in drei Provinzen (Inpres Nr. 1 / 2003). In dieser Verordnung nannte sie die beiden neuen abgeteilten Provinzen „West-Irian-Jaya“ (Vogelkopfregion) und „Mittel-Irian-Jaya“ (Von Timika im Süden bis Biak im Norden). Obwohl noch ohne Rechtsgrundlage, scheint sich die abgespaltene Provinz „West-Irian-Jaya“ de facto zu halten. Der Name bezeichnet zur Zeit nur die Vogelkopfregion, während West-Papua immer noch das gesamte West-Neuguinea bezeichnet.