We present a new algorithm that allows for an efficient evaluation of the Henry coefficient of a guest molecule inside a porous material, which permits to use ab initio energy calculations. The Widom insertion method, which is currently used to compute these Henry coefficients, typically requires millions of energy evaluations. Our new methodology reduces this number by more than 1 order of magnitude, enabling the use of an ab initio potential energy surface. The methodology we propose is reminiscent of the well-known importance sampling technique which is frequently used in Monte Carlo integrations. First, a conventional Widom insertion simulation is performed using a force field. In the second step, the Widom results are used to select a limited number of configurations and only for these configurations the ab initio evaluation of the energy is required. Finally, by appropriately reweighting the latter energies, an accurate estimation of the ab initio Henry coefficient is possible at a moderate computational cost. We apply our methodology to the adsorption of CO2 in Mg-MOF-74, a prototypical case where interactions of a polar guest molecule with unsaturated metal sites dominate the adsorption mechanism. In this case generic force fields such as UFF or Dreiding are inappropriate and the use of ab initio methods is indispensable. In a second case study, we compute Henry coefficients of methane in UiO-66 using different levels of theory. We pay particular attention to the influence of the dispersion corrections and the role of many-body effects. For the final example, we qualitatively investigate adsorption features for a series of functionalized UiO-66 frameworks. Overall the cases we present show that accurate computations of Henry coefficients is extremely challenging, as different levels of theory provide strongly varying results. At the same time ab initio calculations have added value compared to force fields, as they provide a physically more sound description of the adsorption mechanism and in some cases clearly improve correspondence with experiment.