The mammalian olfactory system uses hundreds of specialized G-protein-coupled olfactory receptors (ORs) to discriminate a nearly unlimited number of odorants. Cognate agonists of most ORs have not yet been identified and potential non-olfactory processes mediated by ORs are unknown. Here, we used molecular modeling, fingerprint interaction analysis and molecular dynamics simulations to show that the binding pocket of the prototypical olfactory receptor Olfr73 is smaller, but more flexible, than binding pockets of typical non-olfactory G-protein-coupled receptors. We extended our modeling to virtual screening of a library of 1.6 million compounds against Olfr73. Our screen predicted 25 Olfr73 agonists beyond traditional odorants, of which 17 compounds, some with therapeutic potential, were validated in cell-based assays. Our modeling suggests a molecular basis for reduced interaction contacts between an odorant and its OR and thus the typical low potency of OR-activating compounds. These results provide a proof-of-principle for identifying novel therapeutic OR agonists.