Phase-change storage is widely used in optical information technologies (DVD, CD-ROM and so on), and recently it has also been considered for non-volatile memory applications. This work reports advances in thermal data recording of phase-change materials. Specifically, we show erasable thermal phase-change recording at a storage density of 3.3 Tb inch(-2), which is three orders of magnitude denser than that currently achievable with commercial optical storage technologies. We demonstrate the concept of a thin-film nanoheater to realize ultra-small heat spots with dimensions of less than 50 nm. Finally, we show in a proof-of-concept demonstration that an individual thin-film heater can write, erase and read the phase of these storage materials at competitive speeds. This work provides important stepping stones for a very-high-density storage or memory technology based on phase-change materials.