The discovery of topological insulators, materials with bulk band gaps and protected cross-gap surface states in compounds such as Bi2Se3, has generated much interest in identifying topological surface states (TSSs) in other classes of materials. In particular, recent theoretical calculations suggest that TSSs may be found in half-Heusler ternary compounds. If experimentally realizable, this would provide a materials platform for entirely new heterostructure spintronic devices that make use of the structurally identical but electronically varied nature of Heusler compounds. Here we show the presence of a TSS in epitaxially grown thin films of the half-Heusler compound PtLuSb. Spin- and angle-resolved photoemission spectroscopy, complemented by theoretical calculations, reveals a surface state with linear dispersion and a helical tangential spin texture consistent with previous predictions. This experimental verification of topological behaviour is a significant step forward in establishing half-Heusler compounds as a viable material system for future spintronic devices.