Malay and possibly Chinese traders took spoils and some slaves from western New Guinea for hundreds of years. The first European visitor may have been Jorge de Meneses, who possibly landed on the island in 1526–27 while en route to the Moluccas. The first European attempt at colonization was made in 1793 by Lieut. 

John Hayes, a British naval officer, near Manokwari, now in Papua province, Indonesia. It was the Dutch, however, who claimed the western half of the island as part of the Dutch East Indies in 1828; their control remained nominal until 1898, when their first permanent administrative posts were set up at Fakfak and Manokwari.

Capt. John Moresby of Great Britain surveyed the southeastern coast in the 1870s, and by the 1880s European planters had moved onto New Britain and New Ireland. By 1884 the German New Guinea Company was administering the northeastern quadrant, and a British protectorate was declared over the southeastern quadrant. Despite early gold finds in British New Guinea (which from 1906 was administered by Australia as the colony of Papua), it was in German New Guinea, administered by the German imperial government after 1899, that most early economic activity took place.

Plantations were widely established in the New Guinea islands and around Madang, and labourers were transported from the Sepik River region, the Markham valley, and Buka Island.

Australian forces displaced the German authorities on New Guinea early in World War I, and the arrangement was formalized in 1921, when Australian control of the northeastern quadrant of the island was mandated by the League of Nations. This territory remained administratively separate from Papua, where the protective paternalist policies of Sir Hubert Murray (lieutenant governor of Papua, 1908–40) did little to encourage colonial investment. The discovery in the 1920s of massive gold deposits in eastern New Guinea at the Bulolo River (a tributary of the Markham River) and Edie Creek, near Wau, led to a rush of activity that greatly increased the economic and social impact on the mandated territory compared with those in Papua to the south. In the early 1930s an even greater discovery was made—contact with nearly one million people previously unknown to Europeans who were living in the Highlands basins of the Australian mandate.

During World War II the Japanese army invaded northern New Guinea in early 1942 and took the territorial headquarters in Rabaul. The Japanese were defeated by the Allies (primarily Australian troops) in the Battle of Milne Bay (August–September 1942) in eastern Papua but advanced along the rugged Kokoda Trail almost to the Papuan headquarters at Port Moresby before being pushed back over the mountains, again by Australian troops. The Allied victory in the Battle of the Coral Sea, southwest of the Solomon Islands, saved Port Moresby from a planned Japanese seaborne invasion.

 U.S. forces then moved quickly north and west across the island chain toward Borneo and beyond. Meanwhile, Australian troops continued a costly war on Bougainville Island and the New Guinea mainland until the Japanese surrender in August 1945.