The rapid and aggressive spread of artemisinin-resistant Plasmodium falciparum carrying the C580Y mutation in the kelch13 gene is a growing threat to malaria elimination in Southeast Asia, but there is no evidence of their spread to other regions. We conducted cross-sectional surveys in 2016 and 2017 at two clinics in Wewak, Papua New Guinea (PNG) where we identified three infections caused by C580Y mutants among 239 genotyped clinical samples. One of these mutants exhibited the highest survival rate (6.8%) among all parasites surveyed in ring-stage survival assays (RSA) for artemisinin. Analyses of kelch13 flanking regions, and comparisons of deep sequencing data from 389 clinical samples from PNG, Indonesian Papua and Western Cambodia, suggested an independent origin of the Wewak C580Y mutation, showing that the mutants possess several distinctive genetic features. Identity by descent (IBD) showed that multiple portions of the mutants’ genomes share a common origin with parasites found in Indonesian Papua, comprising several mutations within genes previously associated with drug resistance, such as mdr1, ferredoxin, atg18 and pnp. These findings suggest that a P. falciparum lineage circulating on the island of New Guinea has gradually acquired a complex ensemble of variants, including kelch13 C580Y, which have affected the parasites’ drug sensitivity. This worrying development reinforces the need for increased surveillance of the evolving parasite populations on the island, to contain the spread of resistance.