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.