We report on the spectroscopic detection of supernova SN 2010ma associated with the long gamma-ray burst GRB 101219B. We observed the optical counterpart of the GRB on three nights with the X-shooter spectrograph at the Very Large Telescope. From weak absorption lines, we measure a redshift of z = 0.55. The first-epoch UV-near-infrared afterglow spectrum, taken 11.6 hr after the burst, is well fit by a power law consistent with the slope of the X-ray spectrum. The second-and third-epoch spectra (obtained 16.4 and 36.7 days after the burst), however, display clear bumps closely resembling those of the broad-lined type-Ic SN 1998bw if placed at z = 0.55. Apart from demonstrating that spectroscopic SN signatures can be observed for GRBs at these large distances, our discovery makes a step forward in establishing a general connection between GRBs and SNe. In fact, unlike most previous unambiguous GRB-associated SNe, GRB 101219B has a large gamma-ray energy (E(iso) = 4.2x10(51) erg), a bright afterglow, and obeys the Amati relation, thus being fully consistent with the cosmological population of GRBs.