The structural evolution of negatively charged gold clusters (Au(n)(-)) in the medium size range for n = 27-35 has been investigated using photoelectron spectroscopy (PES) and theoretical calculations. New PES data are obtained using Ar-seeded He supersonic beams to achieve better cluster cooling, resulting in well-resolved spectra and revealing the presence of low-lying isomers in a number of systems. Density-functional theory calculations are used for global minimum searches. For each cluster anion, more than 200 low-lying isomers are generated using the basin-hopping global minimum search algorithm. The most viable structures and low-lying isomers are obtained using both the relative energies and comparisons between the simulated spectra and experimental PES data. The global minimum structures of Au(n)(-) (n = 27, 28, 30, and 32-35) are found to exhibit low-symmetry core-shell structures with the number of core atoms increasing with cluster size: Au(27)(-), Au(28)(-), and Au(30)(-) possess a one-atom core; Au(32)(-) features a three-atom triangular core; and Au(33)(-) to Au(35)(-) all contain a four-atom tetrahedral core. The global searches reveal that the tetrahedral core is a popular motif for low-lying structures of Au(33)(-) to Au(35)(-). The structural information forms the basis for future chemisorption studies to unravel the catalytic effects of gold nanoparticles.