The formation and deposition of solids during the cryogenic processing of natural gas is a perennial risk for operators. Several tools are available for predicting the temperatures at which heavy hydrocarbon solids will form in cryogenic processing equipment; of these the Kohn and Luks Solids Solubility Program (KLSSP)from GPA Midstream has become an industry standard tool for predicting solid-fluid equilibria (SFE)in cryogenic processes. However, although it describes well many of the data sets generated as part of the GPA's research program in the 1970s and 1980s, the KLSSP suffers from limitations including fixed ranges of temperature, mixture composition, no dependence on pressure and a limited set of possible freeze-out components. Here, a new software tool called ThermoFAST is presented, which overcomes these limitations and has been endorsed by GPA Midstream to replace the KLSSP. This model uses a cubic equation of state and efficient flash algorithms to enable rapid calculations of solid-liquid, solid-vapour, and solid-liquid-vapour equilibrium conditions in addition to normal vapour-liquid phase envelopes. The model has been tuned to the available solid-fluid equilibrium literature data for 58 binary mixtures and is able to represent them with an average root-mean-squared temperature deviation of only 1.7 K. It was thoroughly tested against available SLE data for multi-component LNG mixtures, and improved the accuracy of predicted melting temperatures by a factor of 7 relative to KLSSP, with an average rms deviation of only 2.0 K. The rapid flash algorithm was used to identify 26 distinct transition pathways involving solidification phenomena in LNG-relevant fluids: this includes the prediction of retrograde solidification in multiple systems (including the methane + benzene binary)where a decrease in system temperature produces a reduction in the amount of solid phase present.