The nearby radio galaxy M87 offers a unique opportunity for exploring the connection between gamma-ray production and jet formation at an unprecedented linear resolution. However, the origin and location of the gamma-rays in this source is still elusive. Based on previous radio/TeV correlation events, the unresolved jet base (radio core) and the peculiar knot HST-1 at 120 pc from the nucleus are proposed as candidate site(s) of gamma-ray production. Here we report our intensive, high-resolution radio monitoring observations of the M87 jet with the VLBI Exploration of Radio Astrometry (VERA) and the European VLBI Network (EVN) from February 2011 to October 2012, together with contemporaneous high-energy gamma-ray light curves obtained by the Fermi Large Area Telescope. During this period, an elevated level of the M87 flux is reported at TeV with VERITAS. We detected a remarkable flux increase in the radio core with VERA at 22/43 GHz coincident with the VHE activity. Meanwhile, HST-1 remained quiescent in terms of its flux density and structure in the radio band. These results strongly suggest that the TeV gamma-ray activity in 2012 originates in the jet base within 0.03 pc (projected) from the central black hole.