<p>We prove a correspondence, for Riemannian manifolds with self-dual Weyl tensor, between twistor functions and solutions to the Teukolsky equations for any conformal and spin weights. In particular, we give a contour integral formula for solutions to the Teukolsky equations, and we find a recursion operator that generates an infinite family of solutions and leads to the construction of Čech representatives and sheaf cohomology classes on twistor space. Apart from the general conformally self-dual case, examples include self-dual black holes, scalar-flat Kähler surfaces, and quaternionic-Kähler metrics, where we map the Teukolsky equation to the conformal wave equation, establish new relations to the linearised Przanowski equation, and find new classes of quaternionic deformations.</p>