We report the discovery of surface states in the perovskite superconductor [Tl4]TlTe3 (Tl5Te3) and its nonsuperconducting tin-doped derivative [Tl4](Tl0.4Sn0.6)Te3 as observed by angle-resolved photoemission spectroscopy. Density functional theory calculations predict that the surface states are protected by a Z2 topology of the bulk band structure. Specific heat and magnetization measurements show that Tl5Te3 has a superconducting volume fraction in excess of 95%. Thus Tl5Te3 is an ideal material in which to study the interplay of bulk band topology and superconductivity. © 2014 American Physical Society.