There is an urgent need for the discovery of new antileishmanial drugs with a new mechanism of action. Type 2 NADH dehydrogenase from Leishmania infantum (LiNDH2) is an enzyme of the parasite’s respiratory system, which catalyzes the electron transfer from NADH to ubiquinone without coupled proton pumping. In previous studies of the related NADH: ubiquinone oxidoreductase crystal structure from Saccharomyces cerevisiae, two ubiquinone-binding sites (UQI and UQII) were identified and shown to play an important role in the NDH-2-catalyzed oxidoreduction reaction. Based on the available structural data, we developed a three-dimensional structural model of LiNDH2 using homology detection methods and performed an in silico virtual screening campaign to search for potential inhibitors targeting the LiNDH2 ubiquinone-binding site 1—UQI. Selected compounds displaying favorable properties in the computational screening experiments were assayed for inhibitory activity in the structurally similar recombinant NDH-2 from S. aureus and leishmanicidal activity was determined in the wild-type axenic amastigotes and promastigotes of L. infantum. The identified compound, a substituted 6-methoxy-quinalidine, showed promising nanomolar leishmanicidal activity on wild-type axenic promastigotes and amastigotes of L. infantum and the potential for further development.