Registration of pre- to intra-procedural prostate images needs to handle the large changes in position and shape of the prostate caused by varying rectal filling and patient positioning. We describe a probabilistic method for non-rigid registration of prostate images which can quantify the most probable deformation as well as the uncertainty of the estimated deformation. The method is based on a biomechanical Finite Element model which treats the prostate as an elastic material. We use a Markov Chain Monte Carlo sampler to draw deformation configurations from the posterior distribution. In practice, we simultaneously estimate the boundary conditions (surface displacements) and the internal deformations of our biomechanical model. The proposed method was validated on a clinical MRI dataset with registration results comparable to previously published methods, but with the added benefit of also providing uncertainty estimates which may be important to take into account during prostate biopsy and brachytherapy procedures.