A computational (virtual) screening test to identify potential trichomonacidals has been developed. Molecular structures of trichomonacidal and non-trichomonacidal drugs were represented using stochastic and non-stochastic atom-based quadratic indices and a linear discrimination analysis (LDA) was trained to classify molecules regarding their antiprotozoan activity. Validation tests revealed that our LDA-QSAR models recognize at least 88.24% of trichomonacidal lead-like compounds and suggest using this methodology in virtual screening protocols. These classification functions were then applied to find new lead antitrichomonal compounds. In this connection, the biological assays of eight compounds, selected by computational screening using the present models, give good results (87.50% of good classification). In general, most of the compounds showed high activity against Trichomonas vaginalis at the concentration of 100 μg/ml and low cytotoxicity to this concentration. In particular, two heterocyclic derivatives (VA7-67 and VA7-69) maintained their efficacy at 10 μg/ml with an important trichomonacidal activity (100.00% of reduction), but it is remarkable that the compound VA7-67 did not show cytotoxic effects in macrophage cultivations. This result opens a door to a virtual study considering a higher variability of the structural core already evaluated, as well as of other chemicals not included in this study.