The discovery of the life-threatening zoonotic infection Plasmodium knowlesi has added to the challenges of prompt and accurate malaria diagnosis and surveillance. In this study from Aceh Province, Indonesia, a malaria elimination setting where P. knowlesi endemicity was not previously known, we report the laboratory investigation and difficulties encountered when using molecular detection methods for quality assurance of microscopically identified clinical cases. From 2014 to 2015, 20 (49%) P. falciparum, 16 (39%) P. vivax, 3 (7%) P. malariae, and 2 (5%) indeterminate species were identified by microscopy from four sentinel health facilities. At a provincial-level reference laboratory, loop-mediated isothermal amplification (LAMP), a field-friendly molecular method, was performed and confirmed Plasmodium in all samples though further species-identification was limited by the unavailability of non-falciparum species-specific testing with the platform used. At a national reference laboratory, several molecular methods including nested PCR (nPCR) targeting the 18 small sub-unit (18S) ribosomal RNA, nPCR targeting the cytochrome-b (cytb) gene, a P. knowlesi-specific nPCR, and finally sequencing, were necessary to ultimately classify the samples as: 19 (46%) P. knowlesi, 8 (20%) P. falciparum, 14 (34%) P. vivax. Microscopy was unable to identify or mis-classified up to 56% of confirmed cases, including all cases of P. knowlesi. With the nPCR methods targeting the four human-only species, P. knowlesi was missed (18S rRNA method) or showed cross-reactivity for P. vivax (cytb method). To facilitate diagnosis and management of potentially fatal P. knowlesi infection and surveillance for elimination of human-only malaria in Indonesia and other affected settings, new detection methods are needed for testing at the point-of-care and in local reference laboratories.