Chloroquine (CQ) use in Mozambique was stopped in 2002 and artemether-lumefantrine (AL) was implemented in 2008. In light of no use of CQ and extensive use of AL, we determined the frequency of molecular markers of Plasmodium falciparum drug resistance/tolerance to CQ and AL in persons living in Linga-Linga, an isolated peninsula and in Furvela village, which is located 8 km inland. The P. falciparum chloroquine resistance transporter gene CVMNK wild type increased in frequency from 43.9% in 2009 to 66.4% in 2010 (P = 0.001), and combined P. falciparum multidrug resistance gene 1 N86-184F-D1246 haplotype increased significantly between years (P = 0.039). The combination of P. falciparum chloroquine resistance transporter gene CVMNK and P. falciparum multidrug resistance gene NFD increased from 24.3% (2009) to 45.3% in (2010, P = 0.017). The rapid changes observed may largely be caused by decreased use of CQ and large-scale use of AL. In the absence of a clear AL-resistance marker and the (almost) continent-wide use of AL in sub-Saharan Africa, and when considering CQ reintroduction, continued monitoring of these markers is needed.