This paper deals with electron acceleration by a laser pulse in a plasma with a static uniform magnetic field B_{*}. The laser pulse propagates perpendicular to the magnetic field lines with the polarization chosen such that (E_{laser}·B_{*})=0. The focus of the work is on the electrons with an appreciable initial transverse momentum that are unable to gain significant energy from the laser in the absence of the magnetic field due to strong dephasing. It is shown that the magnetic field can initiate an energy increase by rotating such an electron, so that its momentum becomes directed forward. The energy gain continues well beyond this turning point where the dephasing drops to a very small value. In contrast to the case of purely vacuum acceleration, the electron experiences a rapid energy increases with the analytically derived maximum energy gain dependent on the strength of the magnetic field and the phase velocity of the wave. The energy enhancement by the magnetic field can be useful at high laser amplitudes, a_{0}≫1, where the acceleration similar to that in the vacuum is unable to produce energetic electrons over just tens of microns. A strong magnetic field helps leverage an increase in a_{0} without a significant increase in the interaction length.