Fragment-based screening can catalyze drug discovery by identifying novel scaffolds, but this approach is limited by the small chemical libraries studied by biophysical experiments and the challenging optimization process. To expand the explored chemical space, we employ structure-based docking to evaluate orders-of-magnitude larger libraries than those used in traditional fragment screening. We computationally dock a set of 14 million fragments to 8-oxoguanine DNA glycosylase (OGG1), a difficult drug target involved in cancer and inflammation, and evaluate 29 highly ranked compounds experimentally. Four of these bind to OGG1 and X-ray crystallography confirms the binding modes predicted by docking. Furthermore, we show how fragment elaboration using searches among billions of readily synthesizable compounds identifies submicromolar inhibitors with anti-inflammatory and anti-cancer effects in cells. Comparisons of virtual screening strategies to explore a chemical space of 10(22) compounds illustrate that fragment-based design enables enumeration of all molecules relevant for inhibitor discovery. Virtual fragment screening is hence a highly efficient strategy for navigating the rapidly growing combinatorial libraries and can serve as a powerful tool to accelerate drug discovery efforts for challenging therapeutic targets.