Using the density functional theory and generalized gradient approximation for exchange and correlation potential, we have performed an extensive search to obtain the ground state geometries of both neutral and anionic Au(16) cluster by considering over 200 low lying isomers. For the neutral Au(16) cluster we found a new T(d) compact structure to be the lowest energy configuration, which is nearly degenerate in total energy with the previously reported C(s) and C(2v) noncage structures. While the Au(16) (-) cluster, in agreement with previous calculations, is found to have a T(d) hollow cage structure, an isomer with a planar structure is found to be lower in energy. The photoelectron spectra from all the nine lowest energy isomers are calculated and compared with experiment to determine the possibility of their existence. Molecular dynamics simulations on both neutral and anionic Au(16) clusters are carried out to provide further insight into the origin and stability of these structures. Our comprehensive study allows us to answer the following questions: (1) Why are the adiabatic and vertical detachment energies of Au(16) cluster nearly identical when the lowest energy structures of the anion and the neutral are so very different? (2) How is Au(16) (-) formed? Is it born neutral and the extra electron attaches afterwards or is it born anionic and the structure evolves during the electron attachment process?