Parasitic infections caused by the protozoa Trichomonas vaginalis and Giardia intestinalis still represent a major problem in developing countries. Despite the fact that benzimidazoles are promising compounds with activity against both protozoa, systematic studies to characterize and compare their structure–activity relationships (SAR) are limited. Herein, we report a systematic characterization of the SAR of 32 benzimidazoles with activity against T. vaginalis and G. intestinalis. The analysis was based on pairwise comparisons of the activity similarity and molecular similarity using different molecular representations. Radial, MACCS keys, TGD and piDAPH3 fingerprints were used to develop consensus models of the landscape. The landscapes contained continuous regions and activity cliffs. Two ‘deep consensus activity cliffs’ and several pairs of compounds in smooth regions of the SAR were identified in the landscape of T. vaginalis. In contrast, a number of ‘apparent and shallow cliffs’ were found for G. intestinalis. Several compounds active for both parasites showed similar SAR suggesting a common mechanism of action. We also identified pairs of structurally similar molecules with dramatic changes in selectivity. Results suggested that while substitution at position 2 on the benzimidazole moiety plays an important role in increasing the potency against both parasites, substitutions at positions 4–7 could influence selectivity. This study represents a first step towards the systematic characterization of the antiprotozoal activity landscape of benzimidazoles, and has direct implications in the future development of other types of quantitative models. The landscape of larger data sets with other biological endpoints can be analyzed using the general approaches used in this work.