We report on single electronic spins coupled to the motion of mechanical resonators by a novel mechanism based on crystal strain. Our device consists of single-crystal diamond cantilevers with embedded nitrogen-vacancy center spins. Using optically detected electron spin resonance, we determine the unknown spin-strain coupling constants and demonstrate that our system resides well within the resolved sideband regime. We realize coupling strengths exceeding 10 MHz under mechanical driving and show that our system has the potential to reach strong coupling. Our novel hybrid system forms a resource for future experiments on spin-based cantilever cooling and coherent spin-oscillator coupling.