Magnetic relaxation processes were first discussed for a crystal of paramagnetic transition ions(1). It Was suggested that mechanical vibrations of the crystal lattice (phonons) modulate the crystal electric field of the magnetic ion, thus inducing a 'direct' relaxation between two different spin states(1-3). Direct relaxation has also been predicted for single-molecule magnets with a large spin and a high magnetic anisotropy(1,4-7) and was first demonstrated in a Mn-12 acetate crystal(8). The spin-lattice relaxation time for such a direct transition is limited by the phonon density of states at the spin resonance(1). In a three-dimensional system, such as a single-molecule magnet crystal, the phonon energy spectrum is continuous, but in a one-dimensional system, like a suspended carbon nanotube, the spectrum is discrete and can be engineered to an extremely low density of states(9). An individual single-molecule magnet, coupled to a suspended carbon nanotube, should therefore exhibit extremely long relaxation times(9) and the system's reduced size should result in a strong spin-phonon coupling(10,11). Here, we provide the first experimental evidence for a strong spin-phonon coupling between a single molecule spin and a carbon nanotube resonator, ultimately enabling coherent spin manipulation and quantum entanglement(10,11).