Discovering materials that are environmentally stable and also exhibit the necessary collection of properties required for a particular application is a perennial challenge in materials science. Herein, we present an algorithm to rapidly screen materials for their thermodynamic stability in a given environment, using a greedy approach. The performance was tested against the standard energy above the hull stability metric for inert conditions. Using data of 126 320 crystals, the greedy algorithm was shown to estimate the driving force for decomposition with a mean absolute error of 39.5 meV/atom, giving it sufficient resolution to identify stable materials. To demonstrate the utility outside of a vacuum, the in-oxygen stability of 39 654 materials was tested. The enthalpy of oxidation was found to be largely exothermic. Further analysis showed that 1438 of these materials fall into the range required for self-passivation based on the Pilling–Bedworth ratio.