We used the ambient noise cross-correlation and stretching methods to calculate variations in seismic velocities in the region of Volcán de Colima, Mexico. More than 15 years of continuous records were processed, producing long time series of velocity variations related to volcanic activity, meteorological effects, and earthquakes. Velocity variations associated with eruptive activity are tenuous, which probably reflects the open state of the volcano during the study period. Fifteen events among 26 regional tectonic earthquakes produced sharp, temporary decreases in seismic velocities, which then recovered progressively following a linear trend as a function of the logarithm of time. For the 15 events, the amplitude of the perturbation increased almost linearly with the logarithm of the amplitude of the seismic waves that shook the edifice. The most dramatic apparent velocity variation was a drop of up to 2.6% during the nearby M7.4 Tecomán earthquake in 2003. In order to locate the perturbation in the horizontal plane we applied an inverse method based on the radiative transfer approximation. We also used an original approach based on the frequency dependence of velocity variations to estimate the depth of the perturbation. Our results show that the velocity variation was well localized in the shallow layers (< 800 m) of the volcano, with almost no variations occurring outside the edifice. We discuss several possible interpretations and conclude that the most plausible explanation for the velocity decreases is the nonlinear elastic behavior of the granular volcanic material and its mechanical softening induced by transient strains.