Using high-resolution angle-resolved photoemission spectroscopy (ARPES), surface states that were proposed to be useful for constructing the topological superconducting state in sodium cobaltates are experimentally explored. Two energy bands are observed to cross the Fermi level in the large x region. Through in situ surface electron doping, temperature-dependent ARPES measurements, and spin-resolved ARPES measurements, we demonstrate the existence of surface states due to less Na on the surface than in the bulk, as predicted in theory.