The continuous progress in fabricating low-dimensional systems with large spin-orbit couplings has reached a point in which nowadays materials may display spin-orbit splitting energies ranging from a few to hundreds of meV. This situation calls for a better understanding of the interplay between the spin-orbit coupling and other interactions ubiquitously present in solids, in particular when the spin-orbit splitting is comparable in magnitude with characteristic energy scales such as the Fermi energy and the phonon frequency. In this article, the two-dimensional Frohlich electron-phonon problem is reformulated by introducing the coupling to a spin-orbit Rashba potential, allowing for a description of the spin-orbit effects on the electron-phonon interaction. The ground state of the resulting Frohlich-Rashba polaron is studied in the weak and strong-coupling limits of the electron-phonon interaction for arbitrary values of the spin-orbit splitting. The weak-coupling case is studied within the Rayleigh-Schrodinger perturbation theory, while the strong-coupling electron-phonon regime is investigated by means of variational polaron wave functions in the adiabatic limit. It is found that, for both weak- and strong-coupling polarons, the ground-state energy is systematically lowered by the spin-orbit interaction, indicating that the polaronic character is strengthened by the Rashba coupling. It is also shown that, consistently with the lowering of the ground state, the polaron effective mass is enhanced compared to the zero spin-orbit limit. Finally, it is argued that the crossover between weakly and strongly coupled polarons can be shifted by the spin-orbit interaction.