Nonlinear image registration is a challenging task in the field of medical image analysis. In many applications discontinuities may be present in the displacement field, and intensity variations may occur. In this work we therefore utilize an energy functional which is based on Total Variation regularization and a robust data term. We propose a novel, fast and stable numerical scheme to find the minimizer of this energy. Our approach combines a fixed-point procedure derived from duality principles combined with a fast thresholding step. We show experimental results on synthetic and clinical CT lung data sets at different breathing states as well as registration results on inter-subject brain MRIs.