A new experimental procedure is proposed for express evaluation of the coalescence stability of dispersions, in which the dispersed particles undergo solid-liquid phase transition. The procedure includes centrifugation of the dispersion concurrently with the phase transition of the particles and allows precise quantification of dispersion stability in terms of a critical pressure, at which the coalescence between the dispersed particles/drops takes place. The method is applied for studying the effects of surfactant type and concentration on the stability of paraffin-in-water dispersions, which have potential application in energy storage and transportation systems. Several types of water-soluble surfactants (anionic, nonionic, and polymeric) are compared, whereas hexadecane or tetradecane is used as a dispersed phase. Most of the studied individual surfactants are found to be inefficient stabilizers (except for the nonionic Tween 40 and Tween 60). However, the dispersion stability increases significantly after the addition of appropriate cosurfactants, such as hexadecanol, Brij 52, or cocoamidopropyl betaine. Surfactants and cosurfactants with longer hydrophobic tails are better stabilizers than those with shorter tails. The obtained results are discussed from the viewpoint of the mechanisms of particle/drop coalescence during the solid-liquid-phase transition. The consistency and the undercooling temperatures of the studied dispersions are also discussed, because these properties are important for their practical applications. The proposed procedure for evaluation of dispersion stability and some of the conclusions could be relevant to food emulsions, in which dispersed fat particles undergo solid-liquid-phase transition of similar type.