A subset of ultraluminous X-ray sources (those with luminosities of less than 10(40) erg s(-1); ref. 1) are thought to be powered by the accretion of gas onto black holes with masses of similar to 5-20M(circle dot), probably by means of an accretion disk(2,3). The X-ray and radio emission are coupled in such Galactic sources; the radio emission originates in a relativistic jet thought to be launched from the innermost regions near the black hole(4,5), 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(6), and the absorption of soft X-rays in the interstellar medium hinders the determination of 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 in the nearby galaxy M 31, whose peak luminosity exceeded 10(39) erg s(-1). 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 black hole of stellar mass. Continued radio and X-ray monitoring of such sources should reveal the causal relationship between the accretion flow and the powerful jet emission.