Non-equilibrium melting of bulk aluminum during continuous heating at ultra-high heating rates is studied with molecular dynamics simulations. During the simulations, the inter-atomic interactions are described with Sutton-Chen type EAM potential. Strong correlation between the melting behavior and the heating rate are observed. High heating rate will enhance the atomic diffusion and defect formation, and cause the energy and structural difference between the solid and liquid phase to decrease. This will significantly alter the solid phase stability and the barrier for melting, and drive the phase transformation.