Understanding the energetics of molecular adsorption at nanostructured carbon materials opens up to outstanding applications in the postgraphene era. The accurate determination of the adsorbate binding affinity remains however a challenge both experimentally and computationally. Here, we report on the determination of the desorption energy of 25 chemically diverse compounds from graphite using computational methods at different levels of theory: empirical force fields (FF), semiempirical quantum mechanics (SQM), and density functional theory (DFT). By comparing the computational predictions with literature temperature-programmed desorption (TPD) experiments we found that the dispersion-corrected semiempirical method PM6-DH+ yields desorption energies in quantitative agreement with the experiments with an average error of 1.25 kcal mol–1. The discovery of a fast and accurate approach to molecular adsorption at surfaces prompted us to search the chemical space of the adsorbate to optimize the binding affinity for graphene. We found that polarizable groups containing sulfur and halogen atoms significantly enhance the interaction strength with the substrate. In particular, we predict that per-chlorination of aliphatic hydrocarbons doubles the desorption energy from graphene in vacuum. The efficiency of the PM6-DH+ calculations, which allows for screening libraries of compounds, guided the design of potentially improved graphene surfactants, which are commercially available.