Seismic coda waves scattered by small‐scale heterogeneities contain information on stress changes of the medium, because of changes in the physical state of materials. Based on the ultrasonic measurements under different stresses for a cylindrical sandstone sample, we investigate the influence of stress changes on ultrasonic S‐coda attenuation and aim to characterize its stress/frequency‐dependent pattern. Considering the complexity of ultrasonic coda waveforms measured from finite‐size rock samples in laboratory experiments, the Monte Carlo simulation is employed to synthesize ultrasonic envelopes, which act by incorporating the effect of multiple scatterings and boundary reflections on coda waves. The optimal simulation parameters, estimated by minimizing the residual between the observed and synthesized envelopes, indicate that the rock sample under study presents moderate heterogeneities. The relationship between attenuation and stress is similar for direct and coda S waves and remains stable in the range of high‐effective stresses around 30–60 MPa, with less stress sensitivity. Enhanced attenuation for both types of waves occurs at lower‐effective stresses, but with coda attenuation much faster and stronger, presenting a quite different nonlinear behavior with respect to stress. Coda attenuation increases drastically at extremely low‐effective stresses below 15 MPa because of the increase in rock compliance, showing much greater sensitivity to high‐pore pressure than intrinsic attenuation. This study improves our understanding of the mechanism of ultrasonic coda attenuation and its scaling dependence on stress and frequency.