In this paper, a numerical study on the melting behavior of phase change material (PCM) with gradient porous media has been carried out at the pore scales. In order to solve the governing equations, a pore-scale lattice Boltzmann method with the double distribution functions is used, in which a volumetric LB scheme is employed to handle the boundary. The Monte Carlo random sampling is adopted to generate a microstructure of two-dimensional gradient foam metal which are then used to simulate the solid-liquid phase transition in the cavity. The effect of several factors, such as gradient porosity structure, gradient direction, Rayleigh number and particle diameters on the liquid fraction of PCM are systematically investigated. It is observed that the presence of gradient media affect significantly the melting rate and shortens full melting time compared to that for constant porosity by enhancing natural convection. The melting time of positive and negative gradients will change with Rayleigh number, and there is a critical value for Rayleigh number. Specifically, when Rayleigh number is below the critical value, the positive gradient is more advantageous, and when Rayleigh number exceeds the critical value, the negative gradient is more advantageous. Moreover, smaller particle diameters would lead to lower permeability and larger internal surfaces for heat transfer.