Topological crystalline insulators are materials in which the crystalline symmetry leads to topologically protected surface states with a chiral spin texture, rendering them potential candidates for spintronics applications. Using scanning tunneling spectroscopy, we uncover the existence of one-dimensional (1D) midgap states at odd-atomic surface step edges of the three- dimensional topological crystalline insulator (Pb,Sn)Se. A minimal toy model and realistic tight- binding calculations identify them as spin-polarized flat bands connecting two Dirac points. This non-trivial origin provides the 1D midgap states with inherent stability and protects them from backscattering. We experimentally show that this stability results in a striking robustness to defects, strong magnetic fields, and elevated temperature.