The acoustoelastic effect for surface and plate waves propagating in nonuniformly stressed media is analyzed. The theory is based on our earlier perturbation theory and normal mode technique which was used for volume waves. As with the earlier treatment, a Lagrangian description of the motion of the particles in an elastic medium is used. The results are applied to analyze the acoustoelastic effect for Rayleigh waves and Lamb waves in nonuniformly stressed media.