Surface Fermi arcs (SFAs), the unique open Fermi-surfaces (FSs) discovered recently in topological Weyl semimetals (TWSs), are unlike closed FSs in conventional materials and can give rise to many exotic phenomena, such as anomalous SFA-mediated quantum oscillations, chiral magnetic effects, three-dimensional quantum Hall effect, non-local voltage generation and anomalous electromagnetic wave transmission. Here, by using in-situ surface decoration, we demonstrate successful manipulation of the shape, size and even the connections of SFAs in a model TWS, NbAs, and observe their evolution that leads to an unusual topological Lifshitz transition not caused by the change of the carrier concentration. The phase transition teleports the SFAs between different parts of the surface Brillouin zone. Despite the dramatic surface evolution, the existence of SFAs is robust and each SFA remains tied to a pair of Weyl points of opposite chirality, as dictated by the bulk topology.