We report a new technique for sensitive, quantitative and rapid detection of Plasmodium spp.-infected red blood cells (RBCs) by means of magnetic resonance relaxometry (MRR). During the intraerythrocytic cycle, malaria parasites metabolize large amounts of cellular hemoglobin and convert it into hemozoin crystallites. We exploit the relatively large paramagnetic susceptibility of these hemozoin particles, which induce substantial changes in the transverse relaxation rate of proton nuclear magnetic resonance of RBCs, to infer the 'parasite load' in blood. Using an inexpensive benchtop 0.5-Tesla MRR system, we show that with minimal sample preparatory steps and without any chemical or immunolabeling, a parasitemia level of fewer than ten parasites per microliter in a volume below 10 μl of whole blood is detected in a few minutes. We demonstrate this method both for cultured Plasmodium falciparum parasites and in vivo with Plasmodium berghei-infected mice.