Existing Trichomonas vaginalis therapies are out of reach for most trichomoniasis people in developing countries and, where available, they are limited by their toxicity (mainly in pregnant women) and their cost. New antitrichomonal agents are needed to combat emerging metronidazole-resistant trichomoniasis and reduce the side effects associated with currently available drugs. Toward this end, atom-based bilinear indices, a new TOMOCOMD-CARDD molecular descriptor, and linear discriminant analysis (LDA) were used to discover novel, potent, and non-toxic lead trichomonacidal chemicals. Two discriminant functions were obtained with the use of non-stochastic and stochastic atom-type bilinear indices for heteroatoms and H-bonding of heteroatoms. These atomic-level molecular descriptors were calculated using a weighting scheme that includes four atomic labels, namely atomic masses, van der Waals volumes, atomic polarizabilities, and atomic electronegativities in Pauling scale. The obtained LDA-based QSAR models, using non-stochastic and stochastic indices, were able to classify correctly 94.51% (90.63%) and 93.41% (93.75%) of the chemicals in training (test) sets, respectively. They showed large Matthews' correlation coefficients (C); 0.89 (0.79) and 0.87 (0.85), for the training (test) sets, correspondingly. The result of predictions on the 15% full-out cross-validation test also evidenced the robustness and predictive power of the obtained models. In addition, canonical regression analyses corroborated the statistical quality of these models (Rcan of 0.749 and of 0.845, correspondingly); they were also used to compute biological activity canonical scores for each compound. On the other hand, a close inspection of the molecular descriptors included in both equations showed that several of these molecular fingerprints are strongly interrelated with each other. Therefore, these models were orthogonalized using the Randić orthogonalization procedure. These classification functions were then applied to find new lead antitrichomonal agents and six compounds were selected as possible active compounds by computational screening. The designed compounds were synthesized and tested for in vitro activity against T. vaginalis. Out of the six compounds that were designed, and synthesized, three molecules (chemicals VA5-5a, VA5-5c, and VA5-12b) showed high to moderate cytocidal activity at the concentration of 10 μg/ml, other two compounds (VA5-8pre and VA5-8) showed high cytocidal and cytostatic activity at the concentration of 100 μg/ml and 10 μg/ml, correspondingly, and the remaining chemical (compound VA5-5e) was inactive at these assayed concentrations. Nonetheless, these compounds possess structural features not seen in known trichomonacidal compounds and thus can serve as excellent leads for further optimization of antitrichomonal activity. The LDA-based QSAR models presented here can be considered as a computer-assisted system that could potentially significantly reduce the number of synthesized and tested compounds and increase the chance of finding new chemical entities with antitrichomonal activity.