The topology of a topological material can be encoded in its surface states. These surface states can only be removed by a bulk topological quantum phase transition into a trivial phase. Here we use photoemission spectroscopy to image the formation of protected surface states in a topological insulator as we chemically tune the system through a topological transition. Surprisingly, we discover an exotic spin-momentum locked, gapped surface state in the trivial phase that shares many important properties with the actual topological surface state in anticipation of the change of topology. Using a spin-resolved measurement, we show that apart from a surface bandgap these states develop spin textures similar to the topological surface states well before the transition. Our results offer a general paradigm for understanding how surface states in topological phases arise from a quantum phase transition and are suggestive for the future realization of Weyl arcs, condensed matter supersymmetry and other fascinating phenomena in the vicinity of a quantum criticality.