An experimental apparatus was built to measure P-wave velocity (vP) of sandy sediment during hydrate formation from brine and free methane gas. The influences of hydrate saturation, initial brine saturation, conversion ratio of water to hydrate, and grain size of sand upon vP were investigated. The experimental results demonstrate that vP strongly depends on both hydrate saturation and initial brine saturation, whereas the influence of the grain size of sand is unremarkable. During the formation of hydrate for different experimental runs at identical initial brine saturation, vP increases with the increase of hydrate saturation; while it decreases dramatically with the increase of initial brine saturation for a given hydrate saturation. The correlation between vP and conversion ratio of water into hydrate was studied, and it was found that the relation between vP and the conversion ratio of water to hydrate is approximately the same for different experimental runs, regardless of how big the differences in initial saturation of brine and the size of sand grain are. vP was calculated for four different hydrate distribution models. The results suggest that low conversion ratio of water to hydrate, hydrate mainly acts as a load component of a dry frame matrix, whereas at higher conversion ratio of water to hydrate it partly acts as a cement that coats grains at grain contacts, and thereby leads to a dramatic increase in vP. Compared with the hydrate saturation, the conversion ratio of water to hydrate has a large role in distributing hydrate in the pores of sediments.