Extraordinary optical, electrical and chemical properties of 2D materials have potential to be useful for quick and sensitive detection of pathological diseases. One important example is malaria disease that can progress rapidly and cause death within days. Therefore, fast, accurate and cost-effective malaria diagnosis available at the point of care is urgently needed to facilitate precise treatment. Here we report rapid and highly sensitive malaria detection with an inexpensive graphene-protected copper surface plasmon resonance biosensor. Using phase sensitive surface plasmon resonance technique and a graphene functionalization protocol for attaching end-tethered DNA probes that were complementary to a malaria specific DNA target, we were able to significantly improve the detection limit of the malarial plasmodium parasite. The phase sensitivity of our graphene-enhanced sensors exceeds by two orders of magnitude the sensitivity of analogous optical biosensors. This enhanced sensitivity could provide means to detect low copy number bacterial infectious agents and to associate dormant bacterial populations with chronic inflammatory diseases using simple label-free optical detection.