We detect seismic wave velocity changes at Mt. Vesuvius, using doublets and the Coda Wave Interferometry method. The high sensitivity of multiply scattered coda waves to temporal changes in the medium allows us to detect velocity variation smaller than 0.4%. We use 17 doublets, some of them grouped in families of multiplets, spanning January 1996 to December 1999. Data show a systematic increase in velocity from 1996 to end-September 1999, followed by a rapid drop in velocity. This drop immediately precedes a sustained swarm of VT-type earthquakes, including the 9th October 1999 M = 3.6 event, the largest in the region since at least 1972. We propose a long term fluid pressurization followed by influx as a possible causative mechanism.