Brillouin scattering studies have been carried out on high quality single crystals of Fe$_3$O$_4$ with [100] and [110] faces in the temperature range of 300 to 30 K. The room temperature spectrum shows a surface Rayleigh wave (SRW) mode at 8 GHz and a longitudinal acoustic (LA) mode at 60 GHz. The SRW mode frequency shows a minimum at the Verwey transition temperature $T_V$ of 123 K. The softening of the SRW mode frequency from about 250 K to $T_V$ can be quantitatively understood as a result of a decrease in the shear elastic constant C$_{44}$, arising from the coupling of shear strain to charge fluctuations. On the other hand, the LA mode frequency does not show any significant change around $T_V$, but shows a large change in its intensity. The latter shows a maximum at around 120 K in the cooling run and at 165 K in the heating run, exhibiting a large hysteresis of 45 K. This significant change in intensity may be related to the presence of stress-induced ordering of Fe$^{3+}$ and Fe$^{2+}$ at the octahedral sites, as well as to stress-induced domain wall motion. ; Comment: 14 pages, 3 figures, accepted in Physical Review B 2005