An experimental investigation of the effect of random vibration on the melting behavior of a phase change material (PCM) and the thermal performance of a PCM-based heat sink is presented. While random vibration from 2 to 16 g rms for the frequency range from 15 to 2000 Hz was applied to a rectangular enclosure, which contains paraffin wax and the heat sink, a constant heat flux was imposed on the heat sink to melt the PCM. The experimental results showed that the random vibration has no effect on the melting behavior early in the melting process during which conduction is the primary mode of heat transfer. However, the random vibration significantly affected the melting behavior later in the process during which natural convection is the primary mode of heat transfer. The random vibration augmented heat transfer in the molten PCM and increased the Nusselt number, 1.56 times greater under the vibration of 16 g rms than without vibration. The augmented heat transfer accelerated PCM melting and delayed the rise in temperature of the heat sink. The time for the temperature of the heat sink to rise to a threshold increased as the intensity of random vibration increased, 5.9 times longer under the vibration of 16 g rms than without vibration.