We propose a Sparse Bayesian framework for non-rigid registration. Our principled approach is flexible, in that it efficiently finds an optimal, sparse model to represent deformations among any preset, widely overcomplete range of basis functions. It addresses open challenges in state-of-the-art registration, such as the automatic joint estimate of model parameters (e.g. noise and regularization levels). We demonstrate the feasibility and performance of our approach on cine MR, tagged MR and 3D US cardiac images, and show state-of-the-art results on benchmark datasets evaluating accuracy of motion and strain.