Molecular surveillance of drug resistance markers through time provides crucial information on genomic adaptations, especially in parasite populations exposed to changing drug pressures. To assess temporal trends of established genotypes associated with tolerance to clinically important antimalarials used in Kenya over the last two decades, we sequenced a region of the pfcrt locus encompassing codons 72-76 of the Plasmodium falciparum chloroquine resistance transporter, full-length pfmdr1 - encoding multi-drug resistance protein, P-glycoprotein homolog (Pgh1) and pfdhfr encoding dihydrofolate reductase, in 485 archived Plasmodium falciparum positive blood samples collected in coastal Kenya at four different time points between 1995 and 2013. Microsatellite loci were also analyzed to compare the genetic backgrounds of parasite populations circulating before and after the withdrawal of chloroquine and sulfadoxine/pyrimethamine. Our results reveal a significant increase in the prevalence of the pfcrt K76 wild-type allele between 1995 and 2013 from 38% to 81.7% (p < 0.0001). In contrast, we noted a significant decline in wild-type pfdhfr S108 allele (p < 0.0001) culminating in complete absence of this allele in 2013. We also observed a significant increase in the prevalence of the wild-type pfmdr1 N86/Y184/D1246 haplotype from 14.6% in 1995 to 66.0% in 2013 (p < 0.0001) and a corresponding decline of the mutant pfmdr1 86Y/184Y/1246Y allele from 36.4% to 0% in 19 years (p < 0.0001). We also show extensive genetic heterogeneity among the chloroquine-sensitive parasites before and after the withdrawal of the drug in contrast to a selective sweep around the triple mutant pfdhfr allele, leading to a mono-allelic population at this locus. These findings highlight the importance of continual surveillance and characterization of parasite genotypes as indicators of the therapeutic efficacy of antimalarials, particularly in the context of changes in malaria treatment policy.