L'histoire de la Papouasie-Nouvelle-Guinée en tant qu'État souverain ne commence qu'en 1975, mais l'histoire de ce territoire et de sa population remonte à la Préhistoire et comprend de très anciennes traces d'agriculture et de civilisations comme celle de Lapita. Les données archéologiques indiquent que l'homme est arrivé en Nouvelle-Guinée, aux alentours de - ans avant Jésus Christ probablement par l'Asie du Sud-Est lors d'une période glaciaire où l'océan était plus bas et les traversées plus courtes entre les îles. Ces premiers découvreurs sont des chasseurs et cueilleurs. Ils sont les ancêtres des Papous. Il y a environ 10 000 ans, ils développent l'agriculture, faisant de la Nouvelle-Guinée l'une des rares parties du monde à avoir inventé l'agriculture de manière indépendante, et cela bien avant l'Europe ou même la plus grande partie de l'Asie. Ils élèvent des gallinacés, des suidés et cultivent des plants d'igname. Le site agricole de Kuk, classé au patrimoine mondial de l'UNESCO depuis 2008, en demeure l'un des témoins. Il y a quelque 3 500 ans, des migrants austronésiens atteignent la Nouvelle-Guinée orientale et se mêlent aux populations papoues sur la côte septentrionale et dans les îles Bismarck, créant la civilisation de Lapita-Watom. thumb|350px|Carte portugaise incluant la Nouvelle-Guinée, vers l'an 1600. Les premiers Européens à avoir vu la Nouvelle-Guinée furent les navigateurs portugais naviguant dans le Pacifique Sud au début du . Vers 1526, Dom Jorge de Meneses arrive sur l'île principale et la nomme « Papouasie », nom qui provient de papu, que certains auteurs disent dériver d'un mot malais signifient « crépu », comme les cheveux des Mélanésiens (confondus avec les Papous). Le nom de Nouvelle-Guinée est attribué à la région au par un explorateur espagnol en raison de la ressemblance extérieure du pays et des populations locales avec la Guinée d'Afrique et ses habitants. Bien que les navigateurs européens aient régulièrement visité les îles alentour, les habitants restent peu connus des Européens jusque dans les années 1870.