The existence of topological superconductors preserving time-reversal symmetry was recently predicted, and they are expected to provide a solid-state realization of itinerant massless Majorana fermions and a route to topological quantum computation. Their first concrete example, CuxBi2Se3, was discovered last year, but the search for new materials has so far been hindered by the lack of guiding principle. Here, we report point-contact spectroscopy experiments showing that the low-carrier-density superconductor Sn_{1-x}In_{x}Te is accompanied with surface Andreev bound states which, with the help of theoretical analysis, give evidence for odd-parity pairing and topological superconductivity. The present and previous finding of topological superconductivity in Sn_{1-x}In_{x}Te and CuxBi2Se3 demonstrates that odd-parity pairing favored by strong spin-orbit coupling is a common underlying mechanism for materializing topological superconductivity.