The solid-liquid phase change medium (PCM) has many advantages and is widely used in the energy storage device. Under gravity, the solid PCM can have sinking rigid motions in the liquid PCM, which can significantly affect the flow/heat transfer. However, the conventional phase change numerical algorithms are difficult to precisely calculate the sinking rigid motion of the solid PCM. Therefore, this issue needs to be further investigated. In this study, the Euler-Lagrange iteration algorithm is proposed and utilized to calculate the flow/heat transfer and rigid motions in the solid-liquid phase change. Taking the melting and sinking processes of paraffin in a rectangular cavity under gravity as an example, two simulations are carried out using the Euler-Lagrange iteration algorithm and the conventional enthalpy-porous algorithm, respectively. It has been validated that the Euler-Lagrange iteration algorithm can accurately simulate the melting and sinking processes with good numerical stability. During the melting process, the molten liquid paraffin can be extruded from the bottom of the solid paraffin by the sinking rigid motion and generates natural convection cycles along the side walls. The close-contact melting caused by the sinking rigid motion can greatly increase the Nusselt number and heat transfer rate of the bottom wall. Finally, the results can be used to the design and optimization of the solid-liquid phase change device under the external force.