The layered van der Waals antiferromagnet MnBi$_2$Te$_4$ has been predicted to combine the band ordering of archetypical topological insulators such as Bi$_2$Te$_3$ with the magnetism of Mn, making this material a viable candidate for the realization of various magnetic topological states. We have systematically investigated the surface electronic structure of MnBi$_2$Te$_4$(0001) single crystals by use of spin- and angle-resolved photoelectron spectroscopy experiments. In line with theoretical predictions, the results reveal a surface state in the bulk band gap and they provide evidence for the influence of exchange interaction and spin-orbit coupling on the surface electronic structure.