We performed a combined theoretical and experimental photoelectron spectroscopy study of the structural evolution of gold anion clusters Au-n(-) in the size range n = 21-25, a special size range for gold anion clusters where extensive structural changes from the pyramidal structure at Au-20(-) toward the core-shell structure at Au-26(-) were expected to occur. Density functional theory calculations with inclusion of spin-orbit effects were employed to produce the simulated spectra for the selected low-energy isomers obtained from basin-hopping global minimum search. The comparison of these simulated spectra with reasonably well-resolved experimental photoelectron spectra resulted in the identification of the low-lying structures of the gold clusters. The fused-planar and hollow-tubular structures are found dominant in this special size range. The highly stable tetrahedral Au-20 unit (viewed as the fragment of face-centered cubic (FCC) bulk gold) was found intact only in the minor isomer at n = 21, whereas hollow-tubular structures were found prevalent in the n = 22-25 range. At n = 25, the dominant structure is a hollow-tubular one with two of gold pyramids fused together, but not a core-shell one as previously believed.