Using the Saunders “Kick” global search technique combined with density-functional theory calculations, we have performed an extensive search to obtain the ground state geometries of both neutral and anionic Au₁₆ cages doped systematically with an external atom of different valence electrons: Y, Zr, and Nb. The structural and electronic properties of the doped clusters, MAu₁₆^q (M = Y, Zr and Nb; q = 0, −1) are investigated with the aid of previous photoelectron spectroscopy (PES) and theoretical calculations. It is found that the early 4d transition-metals Y, Zr and Nb can be stably encapsulated in the Au₁₆⁻ cage, forming endohedral structures with lager distortion from the parent Au₁₆⁻ cage. Characteristics of the ZrAu₁₆ cluster include its remarkably high average binding energy, doping energy and HOMO–LUMO gap, which reflects its high stability. Furthermore, natural population analysis indicates that a strong ionic bond interaction is revealed in the present study.