Oxygen-doped sodium cluster anions Na(n)O(2) (-) with n=41-148 have been studied by low temperature photoelectron spectroscopy and density functional theory (DFT), with a particular emphasis on those sizes where a spherical electron shell closing is expected. The experimental spectra are in good agreement with the electronic density of states of the DFT lowest energy structures. The cluster structures show segregation between an ionically bonded molecular unit located at the cluster surface and a metallic part. The DFT calculations reveal that each oxygen atom removes two electrons from the metallic electron gas in order to become an O(2-) dianion. A jellium model would therefore predict the electron shell closings to be shifted up by four sodium atoms with respect to pure Na(n) (-) cluster anions. The electron shell closings for Na(n)O(2) (-) are located at n=43, 61, 93, and 139, so the expected four-atom shift is observed only for the small clusters of up to n=61, while a two-atom shift is observed for the larger clusters. The DFT calculations explain this departure from jellium model predictions in terms of a structural transition in the ionically bonded molecular unit.