Indoleamine 2,3-dioxygenase (IDO) is an important therapeutic target for the treatment of diseases such as cancer that involve pathological immune escape. We have used the evolutionary docking algorithm EADock to design new inhibitors of this enzyme. First, we investigated the modes of binding of all known IDO inhibitors. On the basis of the observed docked conformations, we developed a pharmacophore model, which was then used to devise new compounds to be tested for IDO inhibition. We also used a fragment-based approach to design and to optimize small organic molecule inhibitors. Both approaches yielded several new low-molecular weight inhibitor scaffolds, the most active being of nanomolar potency in an enzymatic assay. Cellular assays confirmed the potential biological relevance of four different scaffolds.