We present electronic surface states as obtained by a comprehensive and systematic study of a monolayer of Sb on a relaxed GaAs(110) zinc-blende surface using the first-principles full-potential self-consistent linear muffin tin orbital (LMTO) method. By considering the well accepted epitaxial continued layer structure (ECLS) model we investigate the surface states in the fundamental band gap along high-symmetry directions of the surface Brillouin zone. For the ordered overlayer Sb/GaAs(110), intrinsic surface states appear in the energy gap region which shift towards the bulk valence and the conduction band region when the relaxations of the surface atoms are considered. A detailed analysis of the surface and resonance states reveals that they are in excellent agreement with the available experimental data and the existing pseudopotential calculations.