The accretion of matter onto a massive black hole is believed to feed the relativistic plasma jets found in many active galactic nuclei (AGN). Although some AGN accelerate particles to energies exceeding 1012 electron volts and are bright sources of very-high-energy (VHE) γ-ray emission, it is not yet known where the VHE emission originates. Here we report on radio and VHE observations of the radio galaxy Messier 87, revealing a period of extremely strong VHE γ-ray flares accompanied by a strong increase of the radio flux from its nucleus. These results imply that charged particles are accelerated to very high energies in the immediate vicinity of the black hole.