A subset of ultraluminous X-ray sources (those with luminosities < 10^40 erg/s) are thought to be powered by the accretion of gas onto black holes with masses of ~5-20 M_solar, probably via an accretion disc. The X-ray and radio emission are coupled in such Galactic sources, with the radio emission originating in a relativistic jet thought to be launched from the innermost regions near the black hole, with the most powerful emission occurring when the rate of infalling matter approaches a theoretical maximum (the Eddington limit). Only four such maximal sources are known in the Milky Way, and the absorption of soft X-rays in the interstellar medium precludes determining the causal sequence of events that leads to the ejection of the jet. Here we report radio and X-ray observations of a bright new X-ray source whose peak luminosity can exceed 10^39 erg/s in the nearby galaxy, M31. The radio luminosity is extremely high and shows variability on a timescale of tens of minutes, arguing that the source is highly compact and powered by accretion close to the Eddington limit onto a stellar mass black hole. Continued radio and X-ray monitoring of such sources should reveal the causal relationship between the accretion flow and the powerful jet emission.