Numerical investigation on latent heat thermal energy storage (LHTES) systems with phase change materials (PCMs) vertically heated from one side with novel stepped fins is presented. Transient numerical simulation by using the enthalpy-porosity method is performed to investigate the heat transfer rate and melting behaviors, while the natural convection is considered. To improve the PCM melting process, different upward and downward stepped fins with the step ratios (b/c) of 0.66, 1, 1.5, 2.33 and 4 are employed. The melt fraction and temperature contours by consideration the natural convection effects are presented. The results show that at the beginning of the melting process, the fins in the downward direction with b/c=0.66 improve the PCM melting rate than the other cases, as the part of the heat is well transferred to the bottom of container along the fins and heat is trapped between the heated wall and the fins. The results show that the melting process in all of the tested stepped fins is faster than the conventional horizontal fins. The results show that by using downward stepped fins (b/c=0.4) instead of conventional horizontal fins, the melting process could be enhanced up to 56.3% at t=800sec and 65.5% at t=3600sec.