We report results of ab initio calculations on NaN, N=55, 147 and 309 clusters that show icosahedral growth to be most favorable in agreement with the recent photoelectron spectroscopy data. The icosahedral structures are found to be significantly compressed in the central region. However, a vacancy at the center or the first shell is found to cost much higher energy compared to other sites in the clusters. The vacancy formation energy is the lowest at the vertex sites followed by the edge sites on the cluster surface. These results show that disordering is easier to happen at the surface region of the clusters. Recent experiments on sodium clusters also suggest surface premelting. Furthermore, we obtain a higher value of the vacancy formation energy for N=55 compared to the case of N=147 or 309. This is in agreement with the experimental finding of a higher melting temperature for Na55. The perturbation due to a central vacancy is found to be mainly confined to two atomic shells similar to the phenomena at surfaces of bulk metals. {\textcopyright} 2006 The American Physical Society.