Superluminal motion is a common feature of radio jets in powerful gamma-ray emitting active galactic nuclei. Conventionally, the variable emission is assumed to originate near the central supermassive black-hole where the jet is launched on parsec scales or smaller. Here, we report the discovery of superluminal radio features within a distinct flaring X-ray emitting region in the jet of the nearby radio galaxy M87 with the Very Long Baseline Array. This shows that these two phenomenological hallmarks -- superluminal motion and high-energy variability -- are associated, and we place this activity much further (>=120 pc) from the ``central engine'' in M87 than previously thought in relativistic jet sources. We argue that the recent excess very high-energy TeV emission from M87 reported by the H.E.S.S. experiment originates from this variable superluminal structure, thus providing crucial insight into the production region of gamma-ray emission in more distant blazars.