Il y a environ 21 000 ans, la Nouvelle-Guinée était reliée à l'Australie, formant la masse continentale appelée « Sahul ». L'Australie avait été peuplée il y a au moins 40 000 ans par des migrations depuis l'actuel continent asiatique. Ces migrations ont forcément eu lieu par voie maritime (voir « Ligne Wallace »).
Des migrations avaient également pu avoir eu lieu directement de l'Asie vers la Nouvelle-Guinée et les îles Salomon.
Il y a 5 000 ans (3 000 av. J.-C.), des habitants du littoral de la Chine du Sud, cultivateurs de millet et de riz, commencent à traverser le détroit pour s'installer à Taïwan. Vers 2 000 av. J.-C., des migrations ont lieu de Taïwan vers les Philippines. De nouvelles migrations commencent bientôt des Philippines vers Célèbes et Timor et de là, les autres îles de l'archipel indonésien.
Vers 1 500 av. J.-C., un autre mouvement mène des Philippines sur les côtes et les îles avoisinantes de Nouvelle-Guinée et au-delà, les îles du Pacifique. Les Austronésiens sont sans doute les premiers navigateurs de l'histoire de l'humanité.
Le premier Européen à découvrir l'île fut Antonio de Abreu, un navigateur portugais, en 1511, et le premier à y accoster fut l'explorateur espagnol Jorge de Menezes en 1526. Les Espagnols revendiquèrent l'île en 1546 et la nommèrent Nova Guinea (en latin), car ils pensaient que les indigènes étaient les mêmes que ceux des tribus d'Afrique de l'Ouest. La Nouvelle-Guinée devint un point de chute pour de nombreux autres explorateurs. Les rapports qu'ils firent de la région et l'intérêt scientifique qu'ils suscitèrent furent à l'origine des nombreuses expéditions qui suivirent. En 1793, la Compagnie des Indes orientales revendiqua l'île au nom du Royaume-Uni. La revendication fut disputée par les Pays-Bas et, en 1828, la Compagnie hollandaise des Indes orientales prit possession de la moitié occidentale de la Nouvelle-Guinée.
La partie nord-est, comprenant tous les territoires qui n'étaient pas sous souveraineté anglaise ou hollandaise, fut annexée par l'Allemagne en 1884 sous le nom de Kaiser-Wilhems-Land. Cette même année, le Royaume-Uni prit possession du sud-est, mais en 1906, cette partie fut concédée à l'Australie comme faisant partie du territoire de Papouasie. Les troupes australiennes occupèrent la région allemande en 1914, qui par décision de la Société des Nations devint plus tard un territoire sous mandat australien, et fut renommé le Territoire de Nouvelle-Guinée.
Au cours de la Seconde Guerre mondiale, la Nouvelle-Guinée fut envahie par le Japon et de nombreuses troupes japonaises y demeurèrent jusqu'en septembre 1945. En 1946, le Territoire de Nouvelle-Guinée fut déclaré territoire sous tutelle des Nations unies, administrativement dirigé par l'Australie. Les Pays-Bas abandonnèrent le contrôle de la partie ouest en 1962, qui est devenue la province indonésienne d'Irian Jaya. La partie orientale devint indépendante en tant que Papouasie-Nouvelle-Guinée en 1975. L'intérieur de l'île ne fut vraiment exploré que dans le courant du XXe siècle, et certaines régions de l'intérieur demeurent peu connues.