Topological insulators materialize a topological quantum state of matter where unusual gapless metallic state protected by time-reversal symmetry appears at the edge or surface. Their discovery stimulated the search for new topological states protected by other symmetries, and a recent theory predicted the existence of topological crystalline insulators (TCIs) in which the metallic surface states are protected by mirror symmetry of the crystal. However, its experimental verification has not yet been reported. Here we show the first and definitive experimental evidence for the TCI phase in tin telluride (SnTe) which was recently predicted to be a TCI. Our angle-resolved photoemission spectroscopy shows clear signature of a metallic Dirac-cone surface band with its Dirac point slightly away from the edge of the surface Brillouin zone in SnTe. On the other hand, such a gapless surface state is absent in a cousin material lead telluride (PbTe), in line with the theoretical prediction. Our result establishes the presence of a TCI phase, and opens new avenues for exotic topological phenomena.