Background The simian parasite Plasmodium knowlesi is a common cause of human malaria in Malaysian Borneo and threatens the prospect of malaria elimination. However, little is known about the emergence of P. knowlesi, particularly in Sabah. We reviewed Sabah Department of Health records to investigate the trend of each malaria species over time. Methods Reporting of microscopy-diagnosed malaria cases in Sabah is mandatory. We reviewed all available Department of Health malaria notification records from 1992-2011. Notifications of P. malariae and P. knowlesi were considered as a single group due to microscopic near-identity. Results From 1992-2011 total malaria notifications decreased dramatically, with P. falciparum peaking at 33,153 in 1994 and decreasing 55-fold to 605 in 2011, and P. vivax peaking at 15,857 in 1995 and decreasing 25-fold to 628 in 2011. Notifications of P. malariae/P. knowlesi also demonstrated a peak in the mid-1990s (614 in 1994) before decreasing to ≈ 100/year in the late 1990s/early 2000s. However, P. malariae/P. knowlesi notifications increased >10-fold between 2004 (n = 59) and 2011 (n = 703). In 1992 P. falciparum, P. vivax and P. malariae/P. knowlesi monoinfections accounted for 70%, 24% and 1% respectively of malaria notifications, compared to 30%, 31% and 35% in 2011. The increase in P. malariae/P. knowlesi notifications occurred state-wide, appearing to have begun in the southwest and progressed north-easterly. Conclusions A significant recent increase has occurred in P. knowlesi notifications following reduced transmission of the human Plasmodium species, and this trend threatens malaria elimination. Determination of transmission dynamics and risk factors for knowlesi malaria is required to guide measures to control this rising incidence.