Limiting the increase of CO2 in the atmosphere is one of the largest challenges of our generation(1). Because carbon capture and storage is one of the few viable technologies that can mitigate current CO2 emissions(2), much effort is focused on developing solid adsorbents that can efficiently capture CO2 from flue gases emitted from anthropogenic sources(3). One class of materials that has attracted considerable interest in this context is metal-organic frameworks (MOFs), in which the careful combination of organic ligands with metal-ion nodes can, in principle, give rise to innumerable structurally and chemically distinct nanoporous MOFs. However, many MOFs that are optimized for the separation of CO2 from nitrogen(4-7) do not perform well when using realistic flue gas that contains water, because water competes with CO2 for the same adsorption sites and thereby causes the materials to lose their selectivity. Although flue gases can be dried, this renders the capture process prohibitively expensive(8,9). Here we show that data mining of a computational screening library of over 300,000 MOFs can identify different classes of strong CO2-binding sites-which we term `adsorbaphores'-that endow MOFs with CO2/N-2 selectivity that persists in wet flue gases. We subsequently synthesized two water-stable MOFs containing the most hydrophobic adsorbaphore, and found that their carbon-capture performance is not affected by water and outperforms that of some commercial materials. Testing the performance of these MOFs in an industrial setting and consideration of the full capture process-including the targeted CO2 sink, such as geological storage or serving as a carbon source for the chemical industry-will be necessary to identify the optimal separation material.