The concept of a topological Kondo insulator (TKI) has been brought forward 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 the strong spin-orbit coupling [1-3]. In contrast to other three-dimensional (3D) topological insulators (e.g. Bi2Se3), a TKI is truly insulating in the bulk [4]. Furthermore, strong electron correlations are present in the system, which may interact with the novel topological phase. Applying spin- and angle-resolved photoemission spectroscopy (SARPES) to the Kondo insulator SmB6, a promising TKI candidate, we reveal that the surface states of SmB6 are spin polarized, and the spin is locked to the crystal momentum. Counter-propagating states (i.e. at k and -k) have opposite spin polarizations protected by time-reversal symmetry. Together with the odd number of Fermi surfaces of surface states between the 4 time-reversal invariant momenta in the surface Brillouin zone [5], these findings prove, for the first time, that SmB6 can host non-trivial topological surface states in a full insulating gap in the bulk stemming from the Kondo effect. Hence our experimental results establish that SmB6 is the first realization of a 3D TKI. It can also serve as an ideal platform for the systematic study of the interplay between novel topological quantum states with emergent effects and competing order induced by strongly correlated electrons.