We predict that Coulomb explosion of a nanoscale cluster, which is ionized by high-intensity laser radiation and has a naturally occurring spatial density profile, will invariably produce shock waves. In most typical situations, two shocks, a leading and a trailing one, form a shock shell that eventually encompasses the entire cluster. Being the first example of shock waves on the nanometer scale, this phenomenon promises interesting effects and applications, including high-rate nuclear reactions inside each individual cluster.