A one-phase Stefan problem with latent heat a power function of position is investigated. The second kind of boundary condition is involved, and the surface heat flux is considered as a corresponding power function of time. The problem can be viewed as a special case of the shoreline movement problem under the conditions of nonlinear variation of ocean depth and a surface flux that varies as a power of time. An exact solution is constructed using the similarity transformation technique. Theoretical proof for the existence and the uniqueness of the exact solution is conducted. Solutions for some special cases presented in the literature are recovered. In the end, computational examples of the exact solution are presented, and the results can be used to verify the accuracy of general numerical phase change algorithms. (C) 2013 Elsevier Ltd. All rights reserved.