Raman scattering measurements on BiFeO3 single crystals show an important coupling between the magnetic order and lattice vibrations. The temperature evolution of phonons shows that the lowest energy E and A1 phonon modes are coupled to the spin order up to the Neel temperature. Furthermore, low temperature anomalies associated with the spin re-orientation are observed simultaneously in both the E phonon and the magnon. These results suggest that magnetostriction plays an important role in BiFeO3.