A combined experimental and theoretical study of small gold cluster anions is performed. The experimental effort consists of ion mobility measurements that lead to the assignment of the collision cross sections for the different cluster sizes at room temperature. The theoretical study is based on ab initio molecular dynamics calculations with the goal to find energetically favorable candidate structures. By comparison of the theoretical results with the measured collision cross sections as well as vertical detachment energies (VDEs) from the literature, we assign structures for the small Au-n(-) ions (n<13) and locate the transition from planar to three-dimensional structures. While a unique assignment based on the observed VDEs alone is generally not possible, the collision cross sections provide a direct and rather sensitive measure of the cluster structure. In contrast to what was expected from other metal clusters and previous theoretical studies, the structural transition occurs at an unusually large cluster size of twelve atoms.