Papua, unlike the rest of Indonesia, has had no historic contact with Muslim evangelists, and had its first Christian missionary contact in 1855. With little competition, the mission was relatively successful. Missionaries Carl Ottow and Johann Geisler, under the initiative of Ottho Gerhard Heldring, entered Papua at Mansinam island, near Manokwari on 5 February 1855, and are said to have knelt on the beach and prayed, claiming Papua for Christ. Since 2001, the fifth of February has been a Papuan public holiday, recognizing this first landing.
Ottow and Geisler studied the Numfor language, and were subsequently granted a monthly stipend by the Dutch government. The missionaries proposed a scheme to start a tobacco plantation using Christian Javanese to train the Papuans, and were given 5,000 guilders by the Dutch and two Christian Javanese tobacco farmers. The Dutch administrators perceived the missionaries activities as a cut-price means of colonisation, while the missionaries themselves made profits from trading Papuan goods. The Utrecht Mission Society (UZV) joined the mission from 1863; they were prohibited from trade, and instead established a trading committee.
The UZV established a Christian-based education system as well as regular church services. Initially the Papuans' attendance was encouraged using bribes of betel nut and tobacco, but subsequently this was stopped. In addition, slaves were bought to be raised as step children and then freed. By 1880, only 20 Papuans had been baptised, including many freed slaves.
The Dutch government established posts in Netherlands New Guinea in 1898, a move welcomed by the missionaries, who saw orderly Dutch rule as the essential antidote to Papua paganism. Subsequently the UZV mission had more success, with a mass conversion near Cenderawasih Bay in 1907 and the evangelization of the Sentani people by Pamai, a native Papuan in the late 1920s. Due to the Great Depression, the mission suffered a funding shortfall, and switched to native evangelists, who had the advantage of speaking the local language (rather than Malay), but were often poorly trained. The mission extended in the 1930s to Yos Sudarso Bay, and the UZV mission by 1934 had over 50,000 Christians, 90% of them in North Papua, the remainder in West Papua. By 1942 the mission had expanded to 300 schools in 300 congregations.
The first Catholic presence in Papua was in Fakfak, a Jesuit mission in 1894. In 1902 the Vicariate of Netherlands New Guinea was established. Despite the earlier activity in Fakfak, the Dutch restricted the Catholic Church to the southern part of the island, where they were active especially around Merauke. The mission campaigned against the destructive practices of headhunting and promiscuity among the Marind-anim. Following the 1918 flu pandemic, which killed one in five in the area, the Dutch government agreed to the establishment of model villages, based on European conditions, including wearing European clothes, but which the people would submit to only by violence
In 1925 the Catholics sought to re-establish their mission in Fakfak; permission was granted in 1927. This brought the Catholics into conflict with the Protestants in North Papua, who suggested expanding to South Papua in retaliation. The Catholics and Protestants also began a race for the highlands.
After World War Two, New Guinea remained outside of Indonesian control, under Dutch administration, but in 1963, it was absorbed under dubious circumstances into Indonesia. The Indonesians were suspicious of 'Dutch' elements, which included church teachers and missionaries, who had been educated in Dutch fashion, and began an overnight Indonesianization. Papua acquired a significant population of mostly Muslim transmigrants, who were given land and a house by the Indonesian government. Religious differences as well as cultural with Muslim Indonesian army and administrators have exarcebated the Papua conflict, in which over thousands of Papuans have been killed by Indonesian security forces. Some human right groups like the IWGIA estimate the number of killed Papuans to be over 100,000. The majority of government resources were directed to non-Papuan Muslims rather than Papuan Christians, and non-Papuan Muslims were also given senior administrative roles. Church leaders, suspected of Papuan nationalism, were strictly monitored and in many cases killed where they strayed too close to Papuan separatist movements.