Fewer giants planets are found around M dwarfs than around more massive stars, and this dependence of planetary characteristics on the mass of the central star is an important observational diagnostic of planetary formation theories. In part to improve on those statistics, we are monitoring the radial velocities of nearby M dwarfs with the HARPS spectrograph on the ESO 3.6 m telescope. We present here the detection of giant planets around two nearby M0 dwarfs: planets, with minimum masses of respectively 5 Jupiter masses and 1 Saturn mass, orbit around Gl 676A and HIP 12961. The latter is, by over a factor of two, the most massive planet found by radial velocity monitoring of an M dwarf, but its being found around an early M-dwarf is in app...