Monitoring the genetic structure of pathogen populations may be an economical and sensitive approach to quantify the impact of control on transmission dynamics, highlighting the need for a better understanding of changes in population genetic parameters as transmission declines. Here we describe the first population genetic analysis of the major human malaria parasites, Plasmodium falciparum (Pf) and Plasmodium vivax (Pv) populations following nationwide distribution of long-lasting insecticide treated nets (LLIN) in Papua New Guinea (PNG). Parasite isolates from pre- (2005-6) and post-LLIN (2010-2014) were genotyped using microsatellite markers. Despite parasite prevalence declining substantially (East Sepik: Pf=54.9-8.5%, Pv=35.7-5.6%, Madang: Pf=38.0-9.0%, Pv: 31.8-19.7%), genetically diverse and intermixing parasite populations remained. Pf diversity declined modestly post-LLIN relative to pre-LLIN (East Sepik: Rs = 7.1-6.4, He = 0.77-0.71; Madang: Rs= 8.2-6.1, He = 0.79-0.71). Unexpectedly, population structure present in pre-LLIN populations was lost post-LLIN, suggesting that more frequent human movement between provinces may have contributed to higher gene flow. Pv prevalence initially declined but increased again in one province, yet diversity remained high throughout the study period (East Sepik: Rs=11.4-9.3, He=0.83-0.80; Madang: Rs=12.2-14.5, He=0.85-0.88). Although genetic differentiation values increased between provinces over time, no significant population structure was observed at any time point. For both species, a decline in multiple infections and increasing clonal transmission and significant multilocus linkage disequilibrium (mLD) post-LLIN was a positive indicator of impact on the parasite population using microsatellite markers. These parameters may be useful adjuncts to traditional epidemiological tools in the early stages of transmission reduction.