Background: While Malaysia has had great success in controlling Plasmodium falciparum and Plasmodium vivax, notifications of Plasmodium malariae and the microscopically near-identical Plasmodium knowlesi increased substantially over the past decade. However, whether this represents microscopic misdiagnosis or increased recognition of P. knowlesi has remained uncertain. Methods: To describe the changing epidemiology of malaria in Sabah, in particular the increasing incidence of P. knowlesi, a retrospective descriptive study was undertaken involving a review of Department of Health malaria notification data from 2012–2013, extending a previous review of these data from 1992–2011. In addition, malaria PCR and microscopy data from the State Public Health Laboratory were reviewed to estimate the accuracy of the microscopy-based notification data. Results: Notifications of P. malariae/P. knowlesi increased from 703 in 2011 to 815 in 2012 and 996 in 2013. Notifications of P. vivax and P. falciparum decreased from 605 and 628, respectively, in 2011, to 297 and 263 in 2013. In 2013, P. malariae/P. knowlesi accounted for 62% of all malaria notifications compared to 35% in 2011. Among 1,082 P. malariae/P. knowlesi blood slides referred for PCR testing during 2011–2013, there were 924 (85%) P. knowlesi mono-infections, 30 (2.8%) P. falciparum, 43 (4.0%) P. vivax, seven (0.6%) P. malariae, six (0.6%) mixed infections, 31 (2.9%) positive only for Plasmodium genus, and 41 (3.8%) Plasmodium-negative. Plasmodium knowlesi mono-infection accounted for 32/156 (21%) and 33/87 (38%) blood slides diagnosed by microscopy as P. falciparum and P. vivax, respectively. Twenty-six malaria deaths were reported during 2010–2013, including 12 with ‘P. malariae/P. knowlesi’ (all adults), 12 with P. falciparum (seven adults), and two adults with P. vivax. Conclusions: Notifications of P. malariae/P. knowlesi in Sabah are increasing, with this trend likely reflecting a true increase in incidence of P. knowlesi and presenting a major threat to ...