A key step in phase equilibrium calculations is determining if, in fact, multiple phases are present. Reliably solving the phase stability and, ultimately the phase equilibrium problem, is a significant challenge for high pressure vapor/liquid, liquid/liquid and vapor/liquid/liquid equilibrium. We present the first general-purpose computational method, applicable to any arbitrary equation of state or activity coefficient model, that can mathematically guarantee a correct solution to the phase stability problem. In this paper, we demonstrate the use of this new method, which uses techniques from interval mathematics, for the van der Waals equation of state to determine liquid/liquid and liquid/vapor phase stability for a variety of representative systems. Specifically, we describe and test interval methods for phase stability computations for binary mixtures that exhibit Type I and Type II behavior, as well as for a relatively simple ternary mixture. This shows that interval techniques can find with absolute certainty all stationary points, and thus solve the phase stability problem with complete reliability.