In this paper the implicit time discretization of $E_t - \nabla \cdot K\nabla T = f$, the enthalpy formulation of the Stef an problem, is considered. This generates the algebraic system $E + A\beta (E) = \eta $, where E, $\beta (E)$, $\eta \in {}^ + \mathbb{R}^L $, A is an M-matrix and $\beta (E)$ is the “inverse” of the enthalpy function. The algebraic equation is solved by a modification of the Gauss–Seidel method and convergence is proved. The existence and uniqueness of a weak solution with $T \in W_2^{1,0} (Q_T )$ is established by Rothe’s method. An application to thermal energy storage units which utilize phase change materials is given. Heat transfer via both diffusion and convection of the liquid phase change material is considered.