The hunt for the benchmark topological superconductor (TSc) has been an extremely active research subject in condensed matter research, as it may host Majorana Fermions and enable topological quantum computation. However, so far essentially all TSc candidates have very low transition temperatures (Tc) and/or are very sensitive to disorder and dopant levels, both of which have greatly hampered the progress of this field. Here, we use Angle-resolved Photoemission Spectroscopy (ARPES) to show the presence of Dirac Nodal Lines (DNLs) and corresponding topological surface states (TSSs) on the (010) faces of the Tc=39K s-wave BCS superconductor MgB2. Not only is this nearly triple the current record4 of superconducting Tc among all candidate TScs, but the nature of these DNL states should make them highly tolerant against disorder and inadvertent doping variations. This makes MgB2 a promising high temperature platform for the search and engineering of Majorana fermions.