We study spontaneous bremsstrahlung emission in a highly intense laser field. In this regime the interaction with the laser field has to be treated nonperturbatively by using the relativistic formalism including Dirac-Volkov propagators, while the interaction with the Coulomb field and the bremsstrahlung radiation can be treated in first-order perturbation theory. For the intermediate electron state a fully laser-dressed propagator is used, including radiative corrections to avoid singularities on the mass shell. We find that the use of the Dirac-Volkov propagator is crucial to obtain correct numerical results. The cross section of the process is evaluated for laser intensities of order 10(20) W/cm(2) and relativistic energies of the initial electron.