Through a combination of experimental techniques we show that the topmost layer of the topo- logical insulator TlBiSe$_2$ as prepared by cleavage is formed by irregularly shaped Tl islands at cryogenic temperatures and by mobile Tl atoms at room temperature. No trivial surface states are observed in photoemission at low temperatures, which suggests that these islands can not be re- garded as a clear surface termination. The topological surface state is, however, clearly resolved in photoemission experiments. This is interpreted as a direct evidence of its topological self-protection and shows the robust nature of the Dirac cone like surface state. Our results can also help explain the apparent mass acquisition in S-doped TlBiSe$_2$.