Multi-atlas segmentation has emerged in recent years as a simple yet powerful approach in medical image segmentation. It commonly comprises two steps: (1) a series of pairwise registrations that establish correspondences between a query image and a number of atlases, and (2) the fusion of the available segmentation hypotheses towards labeling objects of interest. In this paper, we introduce a novel approach that solves simultaneously for the underlying segmentation labels and the multi-atlas registration. The proposed approach is formulated as a pairwise Markov Random Field, where registration and segmentation nodes are coupled towards simultaneously recovering all atlas deformations and labeling the query image. The coupling is achieved by promoting the consistency between selected deformed atlas segmentations and the estimated query segmentation. Additional membership fields are estimated, determining the participation of each atlas in labeling each voxel. Inference is performed by using a sequential relaxation scheme. The proposed approach is validated on the IBSR dataset and is compared against standard post-registration label fusion strategies. Promising results demonstrate the potential of our method.