Unii experți consideră că prima menționare cartografică a insulei Papua i-ar aparține celebrului Ptolemeu, sub denumirea „Labadios”. Știm că Ptolemeu a reușit să ofere o reprezentare a lumii greco-romane așa cum era ea cunoscută în secolul al doilea, însă nu avem alte date care să explice de unde anume avea toate aceste informații, dacă proveneau de la călători care ajunseseră acolo sau din alte relatări indirecte.
Așa că dacă îl lăsăm la o parte pe miraculosul Ptolemeu, atunci trebuie să fim atenți la ce au făcut, rând pe rând, până la venirea europenilor după anul 1500, chinezii, persanii, hindușii și, ulterior, populațiile islamizate.
Prima mențiune chineză a unei călătorii în zonă îi aparține unui explorator și negustor din secolul al șaselea, Gao (Ghan) Yu Kuan, care notează în jurnalul său că s-a aprovizionat cu mirodenii din insula Tungki, probabil Papua, dar nu bag mâna în foc. Un secol mai târziu, un alt negustor, Chun Tjok Kwan, tot în căutare de mirodenii, a vizitat Molucele (Maluku) și insula Janggi, aceeași Tungki și probabilă Papua. Numele de „Janggi”era folosit pentru a denumi pasărea paradisului, căci se știe că atunci când reprezentanții regatului Sriwijaya din insula Sumatra i-au oferit împăratului chinez păsări ale paradisului au folosit acest nume.
Tot cam prin secolul al șaptelea au început să ajungă în zona de est a actualuluii arhipelag indonezian corăbiile negustorilor din Persia și India, ocazie cu care au remarcat jungla deasă, impenetrabilă, care nu permitea expedițiile în interiorul insulei. Ne-a rămas o mărturie a vorbitorilor de sanscrită potrivit cărora insula pe care ajunseseră se afla la marginea oceanului, folosind sintagma „Dwi Panta or Samudrananta”.
Hindușii s-au stabilit în arhipelag, mai întâi în Java, acolo unde au construit templul Borobudur, apoi au ajuns și în Bali, acolo îi găsim și astăzi, dând exotism și excentricitate peisajului cu vestitele temple direcționale. Regatul Majapahit a avut relații cu populațiile de pe insulele din zonă, fiind făcute referiri la populația „Srani” din insula Seram a arhipelagului Maluku, cei care aduceau sclavi „Wanin” din vestul insulei Papua pentru a fi folosiți în regat.
O altă mențiune găsim în poemul javanez „Negarakertagama”, scris de Mpu Prapanca prin secolul al XIV-lea în onoarea lui Hayam Wuruk, regele din Majapahit. În poem este folosit numele „Wanin”, în prezent peninsula Onin din Papua de Vest. Unii istorici consideră că relatarea nu trebuie considerată un izvor istoric, fiind vorba de ficțiune poetică.
Mult mai sigure sunt relațiile dintre Regatul islamic Tidore din insulele Maluku și vecinii lor papuași. Se știe că, în perioada în care europenii începeau marile lor călătorii, o flotilă de ambarcațiuni tradiționale „kora-kora” condusă de sultanul Ibn Mansyur s-a încheiat cu inculderea în regat a unor zone de țărm ale insulei Papua. Acum, în timpul regatului Tidore, începe să fie folosit numele “Papa-Ua” pentru acest teritoriu inclus pe harta regatului. Cu privire la înțelesul acestei expresii sunt păreri diferite, așa că le menționez pe toate, fiecare în parte interesantă. După unii ar însemna „neinclus în regat”, după alții „teritoriu fără rege (conducător)”, în fine, după alții, care iau în considerare alte filiații lingvistice, „acolo unde sunt oameni cu părul creț”. Toate denumirile sunt acceptabile pentru că, într-adevăr, regatul Tidore nu a stăpânit Papua, papuașii aveau organizare tribală, fără un lider unificator, în fine, papuașii au părul creț.
Este sigur faptul că zona de coastă a insulei Papua a devenit din ce în ce mai interesantă economic în timpul Sultanatului Tidore, fiind cuprinsă într-o federație comercială aflată în concurență cu altă federație consudă de Sultanatul Ternate. Principalele mărfuri erau rășinile, mirodeniile, sclavii și penele foarte scumpe ale păsării paradisului. Se știe că erau trei zone de coastă care erau sub controlul Sultanatului Tidore, relațiile dintre acestea și centru fiind de vasalitate.
Cam așa stăteau lucrurile la începutul secolului al XVI-lea, perioada în care au început să vină exploratorii și comercianții europenii, ceea ce a dus la declinul sultanatelor și la preluarea inițiativei mai întâi de către portughezi, apoi de către olandezi. Sursele istorice mai târzii îl menționează pe sultanul Nuku, un rebel din jurul anului 1780, care s-a revoltat împotriva olandezilor și s-ar fi proclamat „Sultan peste Tidore și Papua”.
Să recapitulăm. Înainte de venirea europenilor, insula Papua a fost cunoscută de navigatori și comercianți veniți din China, India și Persia. În insulele Sumatra și Java s-au constituit formațiuni statale, mai întâi de influență hindusă, apoi islamică, iar aceste regate și sultanate, în înaintarea lor spre est, au avut interese comerciale care au vizat țărmul insulei Papua sau Noua Guinee, îi puteți zice cum vă place. Europenii au ajuns tot numai în zonele de coastă ale insulei. Teritoriul din centrul insulei, zona înaltă cu jungla deasă, a rămas impenetrabil și neexplorat, iar triburile de acolo și-au continuat modul tradițional de viață, rămânând în același stadiu de dezvoltare până în secolul douăzeci, atunci când au început să fie descooperite și contactate.