We study the entanglement spectra of surface states of symmetry-protected topological phases. The topological bulk imprints the surface with an anomaly that does not permit it to form a trivial "vacuum"state that is gapped, unfractionalized, and symmetry preserving. Any surface wave function encodes the topology of the underlying bulk in addition to a specific surface phase. We show that the real-space entanglement spectrum of such surface wave functions are dominated by the bulk topology and do not readily permit identifying the surface phase. We thus use a modified form of entanglement spectra that incorporates the anomaly and argue that they correspond to physical edge states between different surface states. We support these arguments by explicit analytical and numerical calculations for free and interacting surfaces of three-dimensional topological insulators of electrons.