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 10^12 electron Volts (eV) and are bright sources of very-high-energy (VHE) gamma-ray emission, it is not yet known where the VHE emission originates. Here we report on radio and VHE observations of the radio galaxy M87, revealing a period of extremely strong VHE gamma-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.