The recent discovered antiferromagnetic topological insulators in Mn-Bi-Te family with intrinsic magnetic ordering have rapidly drawn broad interest since its cleaved surface state is believed to be gapped, hosting the unprecedented axion states with half-integer quantum Hall effect. Here, however, we show unambiguously by using high-resolution angle-resolved photoemission spectroscopy that a gapless Dirac cone at the (0001) surface of MnBi$_2$Te$_4$ exists between the bulk band gap. Such unexpected surface state remains unchanged across the bulk N\'eel temperature, and is even robust against severe surface degradation, indicating additional topological protection. Through symmetry analysis and $\textit{ab}$-$\textit{initio}$ calculations we consider different types of surface reconstruction of the magnetic moments as possible origins giving rise to such linear dispersion. Our results reveal that the intrinsic magnetic topological insulator hosts a rich platform to realize various topological phases such as topological crystalline insulator and time-reversal-preserved topological insulator, by tuning the magnetic configurations.
