It is a central challenge for energy self-supplied underwater vehicles converting the huge ocean thermal energy to electrical energy effectively. However, the energy storage efficiency of ocean thermal energy storage (OTES) unit limits the conversion efficiency. Fins are proposed for OTES unit to improve energy storage efficiency in this paper. Firstly, this paper develops a non-stationary model of solidification heat transfer for OTES unit and uses FLUENT to accomplish its numerical analysis. Then, the influence of radial fin and fractal fin on the solidification behavior of phase change material (PCM) are compared. Finally, several fractal fins with different fractal levels, bifurcation angles and ambient temperature are analyzed for the evolution of the liquid phase rate and temperature distribution of PCM. The results show that fractal fins can reduce the solidification time of PCM by 34.46% compared with radial fins. Furthermore, the solidification rate of PCM can be improved by increasing the number of fractal levels and choosing a proper bifurcation angle. However, the solidification behavior of PCM changes slightly when the fractal level increases to 3. The bifurcation angle of 90° is appropriate for practical applications. Furthermore, keeping the temperature difference above 10K can achieve faster solidification.