We have previously reported that sulfated cyclodextrins inhibit the invasion of Plasmodium merozoites by interacting with receptors present on the surface of erythrocytes. The observation that tetrazolium salts formed stable complexes with the inhibitory sulfated cyclodextrins suggested that tetrazolium salts might have anti-Plasmodium activity as well. Evaluation of commercially available tetrazolium salts indicated that some were active in the low nanomolar range and showed specificity in their inhibition of Plasmodium. Synthesis of a further 54 structures allowed us to determine that activity results from an aromatic component attached to the tetrazolium carbon atom (R1) and its size is not critical to the activity of the compound. Nitro modifications of active compounds are poorly tolerated, however, the presence of halogen atoms on aromatic groups attached to the nitrogen atoms of the tetrazolium ring (R2 and R3) has little effect on activity. Methoxy groups are tolerated on R2 and R3 components; however, they are disruptive on the R1 component. The overall results suggest that the R1 component is interacting with a specific hydrophobic environment and the R2 and R3 components are less constrained. The activity of these compounds in several human and mouse Plasmodium cultures suggests that the compounds interact with a component of the parasite that is both essential and conserved.