New biomarkers have to be developed in order to increase the performance of current antigen-based malaria rapid diagnosis. Antibody production often involves the use of laboratory animals and is time-consuming and costly, especially when the target is Plasmodium, whose variable antigen expression complicates the development of long-lived biomarkers. To circumvent these obstacles, we have applied the Systematic Evolution of Ligands by EXponential enrichment method to the rapid identification of DNA aptamers against Plasmodium falciparum-infected red blood cells (pRBCs). Five 70 b-long ssDNA sequences, and their shorter forms without the flanking PCR primer-binding regions, have been identified having a highly specific binding of pRBCs versus non-infected erythrocytes. Structural analysis revealed G-enriched sequences compatible with the formation of G-quadruplexes. The selected aptamers recognized intracellular epitopes with apparent Kds in the μM range in both fixed and non-fixed saponin-permeabilized pRBCs, improving >30-fold the pRBC detection in comparison with aptamers raised against Plasmodium lactate dehydrogenase, the gold standard antigen for current malaria diagnostic tests. In thin blood smears of clinical samples the aptamers reported in this work specifically bound all P. falciparum stages versus non-infected erythrocytes, and also detected early and late stages of the human malaria parasites Plasmodium vivax, Plasmodium ovale and Plasmodium malariae. The results are discussed in the context of their potential application in future malaria diagnostic devices.