Topological Kondo insulators have been proposed as a new class of topological insulators in which non-trivial surface states reside in the bulk Kondo band gap at low temperature due to strong spin-orbit coupling. In contrast to other three-dimensional topological insulators, a topological Kondo insulator is truly bulk insulating. Furthermore, strong electron correlations are present in the system, which may interact with the novel topological phase. By applying spin- and angle-resolved photoemission spectroscopy, here we show that the surface states of SmB6 are spin polarized. The spin is locked to the crystal momentum, fulfilling time reversal and crystal symmetries. Our results provide strong evidence that SmB6 can host topological surface states in a bulk insulating gap stemming from the Kondo effect, which can serve as an ideal platform for investigating of the interplay between novel topological quantum states with emergent effects and competing orders induced by strongly correlated electrons.