Efficient conversion of electromagnetic energy to particle energy is of fundamental importance in many areas of physics. A promising avenue for producing matter with unprecedented energy densities is by heating atomic clusters, an intermediate form of matter between molecules and solids(1), with high-intensity, ultra-short light pulses(2-4). Studies of noble-gas clusters heated with high-intensity (>10(16)W cm(-2)) laser pulses indicate that a highly ionized, very high temperature micro-plasma is produced. The explosion of these superheated clusters ejects ions with substantial kinetic energy(3-5), Here we report the direct measurement of the ion energy distributions resulting from these explosions. We find, in the case of laser-heated xenon clusters, that such explosions produce xenon ions with kinetic energies up to 1 MeV. This energy is four orders of magnitude higher than that achieved in the Coulomb explosion of small molecules(6), indicating a fundamental difference in the nature of intense laser-matter interactions between molecules and clusters. Moreover, it demonstrates that access to an extremely high temperature state of matter is now possible with small-scale lasers.