Topological superconductors (TSCs), with the capability to host Majorana bound states that can lead to non-Abelian statistics and application in quantum computation, have been one of the most intensively studied topics in condensed matter physics recently. Up to date, only a few compounds have been proposed as candidates of intrinsic TSCs, such as doped topological insulator CuxBi2Se3 and iron-based superconductor FeTe0.55Se0.45. Here, by carrying out synchrotron and laser based angle-resolved photoemission spectroscopy (ARPES), we systematically investigated the electronic structure of a quasi-1D superconductor TaSe3, and identified the nontrivial topological surface states. In addition, our scanning tunneling microscopy (STM) study revealed a clean cleaved surface with a persistent superconducting gap, proving it suitable for further investigation of potential Majorana modes. These results prove TaSe3 as a stoichiometric TSC candidate that is stable and exfoliable, therefore a great platform for the study of rich novel phenomena and application potentials.