A new class of gold nanostructures has been fabricated on the (100), (111), and (110) surfaces of lattice-matched MgAl(2)O(4) substrates. The nanostructures were fabricated through a synthesis route where a thin gold film dewets, liquefies, and then slowly self-assembles. The supported nanostructures are intricately shaped, crystalline, and epitaxially aligned. Simulations based on a continuum elastic theory indicate that the self-assembly is driven by strained epitaxy and minimization of the surface free energy.