Low-temperature scanning tunneling spectroscopy over Co nanoislands on Cu(111) showed that the surface states of the islands vary with their size. Occupied states exhibit a sizable downward energy shift as the island size decreases. The position of the occupied states also significantly changes across the islands. Atomic-scale simulations and ab initio calculations demonstrate that the driving force for the observed shift is related to size-dependent mesoscopic relaxations in the nanoislands.