We introduce a novel discrete optimization method for non-rigid image registration based on the random walker algorithm. We discretize the space of deformations and formulate registration using a Gaussian MRF where continuous labels correspond to the probability of a point having a certain discrete deformation. The interaction (regularization) term of the corresponding MRF energy is convex and image dependent, thus being able to accommodate different types of tissue elasticity. This formulation results in a fast algorithm that can easily accommodate a large number of displacement labels, has provable robustness to noise and a close to global solution. We experimentally demonstrate the validity of our formulation on synthetic and real medical data.