Stishovite (rutile-type SiO2) is the archetype of dense silicates and may occur in post-garnet eclogitic rocks at lower-mantle conditions. Sound velocities in stishovite are fundamental to understanding its mechanical and thermodynamic behavior at high pressure and temperature. Here, we use plate-impact experiments combined with velocity interferometry to determine the stress, density, and longitudinal sound speed in stishovite formed during shock compression of fused silica at 44 GPa and above. The measured sound speeds range from 12.3(8) km/s at 43.8(8) GPa to 9.8(4) km/s at 72.7(11) GPa. The decrease observed at 64 GPa reacts a decrease in the shear modulus of stishovite, likely due to the onset of melting. By 72 GPa, the measured sound speed agrees with the theoretical bulk sound speed indicating loss of all shear stiffness due to complete melting. Our sound velocity results provide direct evidence for shock-induced melting, in agreement with previous pyrometry data.