Magnetic relaxation processes were first discussed for a crystal of paramagnetic transition ions. 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. Direct relaxation has also been predicted for single-molecule magnets with a large spin and a high magnetic anisotropy and was first demonstrated in a Mn12 acetate crystal. The spin-lattice relaxation time for such a direct transition is limited by the phonon density of states at the spin resonance. 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. An individual single-molecule magnet, coupled to a suspended carbon nanotube, should therefore exhibit extremely long relaxation times and the system's reduced size should result in a strong spin-phonon coupling. 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.