Here the electron-phonon Holstein model with Rashba spin-orbit interaction is studied for a two-dimensional square lattice in the adiabatic limit. It is demonstrated that a delocalized electron at zero spin-orbit coupling localizes into a large polaron state as soon as the Rashba term is nonzero. This spin-orbit induced polaron state has localization length inversely proportional to the Rashba coupling gamma and it dominates a wide region of the gamma-lambda phase diagram, where lambda is the electron-phonon interaction.