The laws governing the propagation of elastic surface Rayleigh waves along flat and curved boundaries of bodies with initial (residual) stresses are studied. Within the framework of the linearized theory of elasticity, the dispersion equations are obtained for determining the phase velocities of surface Rayleigh waves. In this case, cylindrical bodies (an infinite continuous cylinder and a cylindrical cavity), as well as a sphere under the action of a preliminary all-round load, are considered. Recent studies are closely related to contact problems (to establish the phenomena of “resonant nature”). In addition, such studies have independent significance. Qualitative and quantitative effects of the influence of the initial (residual) stresses on the nature of wave processes are obtained. For this work, it is characteristic and general that, firstly, all the main bodies examined are elastic; secondly, all the bases (bodies) are prestressed.