The calculation of solid-fluid equilibrium at high pressure is important in the modeling and design of processes that use supercritical fluids to selectively extract solid solutes. We describe here a new method for reliably computing solid-fluid equilibrium at constant temperature and pressure or for verifying the nonexistence of a solid-fluid equilibrium state at the given conditions. Difficulties that must be considered include the possibility of multiple roots to the equifugacity conditions and multiple stationary points in the tangent plane distance analysis done for purposes of determining global phase stability. Somewhat surprisingly, these issues are often not dealt with by those who measure, model, and compute high-pressure solid-fluid equilibria, leading in some cases to incorrect or misinterpreted results. It is shown here how these difficulties can be addressed by using a methodology based on interval analysis, which can provide a mathematical and computational guarantee that the solid-fluid equilibrium problem is correctly solved. The technique is illustrated with several example problems in which the Peng-Robinson equation of state model is used. However, the methodology is of general purpose and can be applied in connection with any model of the fluid phase.