Background: In response to chloroquine (CQ) resistance, the policy for the first-line treatment of uncomplicated malaria in the Democratic Republic of East Timor (DRET) was changed in early 2000. The combination of sulphadoxine-pyrimethamine (SP) was then introduced for the treatment of uncomplicated falciparum malaria. Methods: Blood samples were collected in two different periods (2003-2004 and 2004-2005) from individuals attending hospitals or clinics in six districts of the DRET and checked for Plasmodium falciparum infection. 112 PCR-positive samples were inspected for genetic polymorphisms in the pfcrt, pfmdr1, pfdhfr and pfdhps genes. Different alleles were interrogated for potential associations that could be indicative of non-random linkage. Results: Overall prevalence of mutations associated with resistance to CQ and SP was extremely high. The mutant form of Pfcrt (76T) was found to be fixed even after five years of alleged CQ removal. There was a significant increase in the prevalence of the pfdhps 437G mutation (X-2 = 31.1; p = 0.001) from the first to second survey periods. A non-random association was observed between pfdhfr51/pfdhps437 (p = 0.001) and pfdhfr 59/pfdhps 437 (p = 0.013) alleles. Conclusion: Persistence of CQ-resistant mutants even after supposed drug withdrawal suggests one or all of the following: local P. falciparum may still be inadvertently exposed to the drug, that mutant parasites are being "imported" into the country, and/or reduced genetic diversity and low parasite transmission help maintain mutant haplotypes. The association between pfdhfr51/pfdhps437 and pfdhfr 59/pfdhps 437 alleles indicates that these are undergoing concomitant positive selection in the DRET.