We investigate the influence of the Coulomb interaction on laser-assisted Mott scattering. This is done by using an approximation in which the initial state of the electron is described by a Coulomb function modulated by the laser in the same way as a relativistic Volkov state. Numerical calculations are carried out for medium field intensity, and compared with the corresponding results obtained within the first-order Born approximation (where Coulomb distortion effects are neglected). It is found that the differential cross sections of the present treatment agree well with the Born predictions at small angles. With increasing scattering angles, however, including the Coulomb interaction enhances the cross section, as compared to the first-Born results. Furthermore, we show that the Coulomb distortion of the electron motion leads to a qualitatively different dependence of the cross sections on the laser frequency at high frequencies. The dependences of the differential cross section on the other field parameters, impact energy and the charge state of the residual ion are also studied.