The discovery of two-dimensional (2D) systems hosting intrinsic long-range magnetic order represents a seminal addition to the rich physical landscape of van der Waals (vdW) materials. CrI3 has emerged as perhaps the most salient example, as the interdependence of crystalline structure and magnetic order, along with strong light-matter interactions provides a promising platform to explore the optical control of magnetic, vibrational, and charge degrees of freedom at the 2D limit. However, the fundamental question of how this relationship between structure and magnetism manifests on their intrinsic timescales has rarely been explored. Here, we use ultrafast optical spectroscopy to probe magnetic and vibrational dynamics in CrI3, revealing demagnetization dynamics governed by spin-flip scattering and remarkably, a strong transient exchange-mediated interaction between lattice vibrations and spin oscillations. The latter yields a coherent spin-coupled phonon mode that is highly sensitive to the helicity of the driving pulse in the magnetically ordered phase. Our results shed light on the nature of spin-lattice coupling in vdW magnets on ultrafast timescales and highlight their potential for applications requiring non-thermal, high-speed control of magnetism at the nanoscale.