Genetic epidemiology can provide important insights into parasite transmission that can inform public health interventions. The current study compared long-term changes in the genetic diversity and structure of co-endemic Plasmodium falciparum and P. vivax populations. The study was conducted in Papua Indonesia, where high-grade chloroquine resistance in P. falciparum and P. vivax led to a universal policy of Artemisinin-based Combination Therapy (ACT) in 2006. Microsatellite typing and population genetic analyses were undertaken on available isolates collected between 2004 and 2017 from patients with uncomplicated malaria (n = 666 P. falciparum and n = 615 P. vivax). The proportion of polyclonal P. falciparum infections fell from 28% (38/135) before policy change (2004-2006) to 18% (22/125) at the end of the study (2015-2017); p<0.001. Over the same period, polyclonal P. vivax infections fell from 67% (80/119) to 35% (33/93); p<0.001. P. falciparum strains persisted for up to 9 years compared to 3 months for P. vivax, reflecting higher rates of outbreeding in the latter. Sub-structure was observed in the P. falciparum population, but not in P. vivax, confirming different patterns of outbreeding. The P. falciparum population exhibited 4 subpopulations that changed in frequency over time. Notably, a sharp rise was observed in the frequency of a minor subpopulation (K2) in the late post-ACT period, accounting for 100% of infections in late 2016-2017. The results confirm epidemiological evidence of reduced P. falciparum and P. vivax transmission over time. The smaller change in P. vivax population structure is consistent with greater outbreeding associated with relapsing infections and highlights the need for radical cure to reduce recurrent infections. The study emphasizes the challenge in disrupting P. vivax transmission and demonstrates the potential of molecular data to inform on the impact of public health interventions.