Phase boundaries for five synthetic paraffinic mixtures were predicted using a previously developed Gibbs energy minimization algorithm. In this method, the vapour and liquid phases were described by cubic equations of state (EoS). These EoS employed a predictive temperature-dependent group-contribution binary interaction parameter model. The solid phase was described using a universal quasi-chemical activity coefficient (UNIQUAC) solid solution model. Using this algorithm, the phase boundaries were calculated from a temperature-search strategy. The predicted phase boundaries were found to be in good agreement with experimental phase boundaries for vapour-liquid (VL), solid-liquid (SL), solid-vapour (SV), and solid-vapour-liquid (SVL) regions. The model was also used to predict the phase boundaries at low temperatures where no experimental data were available.