Heating of over-dense plasma represents a long-standing quest in laser–plasma physics. When the strength of the magnetic field is above the critical value, a right-handed circularly polarized laser could propagate into and heat up the highly magnetized over-dense collisional plasma directly; the processes are dependent on the parameters of the laser, plasma and magnetic field. The parametric dependence is fully studied both qualitatively and quantitatively, resulting in scaling laws of the plasma temperature, heating depth and energy conversion efficiency. Such heating is also studied with the most powerful CO2 and strongest magnetic field in the world, where plasma with density of ${10}^{23}$ cm–3 and initial temperature of 1 keV is heated to around 10 keV within a depth of several micrometres. Several novel phenomena are also discovered and discussed, that is, local heating in the region of high density, low temperature or weak magnetic field.