The human malaria parasite Plasmodium vivax is more resistant to malaria control strategies than Plasmodium falciparum, and maintains high genetic diversity even when transmission is low. To investigate whether declining P. vivax transmission leads to increasing population structure that would facilitate elimination, we genotyped samples from across the Southwest Pacific region, which experiences an eastward decline in malaria transmission, as well as samples from two time points at one site (Tetere, Solomon Islands) during intensified malaria control. Analysis of 887 P. vivax microsatellite haplotypes from hyperendemic Papua New Guinea (PNG, n = 443), meso-hyperendemic Solomon Islands (n = 420), and hypoendemic Vanuatu (n = 24) revealed increasing population structure and multilocus linkage disequilibrium yet a modest decline in diversity as transmission decreases over space and time. In Solomon Islands, which has had sustained control efforts for 20 years, and Vanuatu, which has experienced sustained low transmission for many years, significant population structure was observed at different spatial scales. We conclude that control efforts will eventually impact P. vivax population structure and with sustained pressure, populations may eventually fragment into a limited number of clustered foci that could be targeted for elimination.