The atomic structures of bare gold clusters provide the foundation to understand the enhanced catalytic properties of supported gold nanoparticles. However, the richness of diverse structures and the strong relativistic effects have posed considerable challenges for a systematic understanding of gold clusters with more than 20 atoms. We use photoelectron spectroscopy of size-selected anions, in combination with first principles calculations, to elucidate the structures of gold nanoclusters in a critical size regime from 55 to 64 atoms (1.1-1.3 nm in diameter). Au(55)(-) is found to be a nonicosahedral disordered cluster as a result of relativistic effects that induce strong surface contractions analogous to bulk surface reconstructions, whereas low-symmetry core-shell-type structures are found for Au(56)(-) to Au(64)(-). Au(58) exhibits a major electron-shell closing and is shown to possess a low-symmetry, but nearly spherical structure with a large energy gap. Clear spectroscopic and computational evidence has been observed, showing that Au(58)(-) is a highly robust cluster and additional atoms are simply added to its surface from Au(59)(-) to Au(64)(-) without inducing significant structural changes. The unique low-symmetry structures characteristic of gold nanoclusters due to the strong relativistic effects allow abundant surface defects sites, providing a key structure-function relationship to understand the catalytic capabilities of gold nanoparticles.