The structures and electronic properties of low-energy neutral and anionic Mg (n = 3-20) clusters have been studied by utilizing a widely adopted CALYPSO structure searching method coupled with density functional theory calculations. A large number of low-energy isomers are optimized at the B3PW91 functional with the 6-311+G(d) basis set. The optimized geometries clearly indicate that a structural transition from hollow three-dimensional configurations to filled-cage-like structures occurs at n = 16 for both neutral and anionic clusters. Based on the anionic ground state structures, photoelectron spectra are simulated using time-dependent density functional theory (TD-DFT) and compared with experimental results. The good agreement validates that the current ground state structures, obtained from the symmetry-unconstrained searches, are true global minima. A detailed chemical bonding analysis distinctly indicates that the Mg-17 cluster is the first neutral locally pi-aromatic homonuclear all-metal cluster, which perfectly satisfies Huckel's well-known 4N + 2 rule.