Multi-atlas segmentation is commonly performed in two separate steps: i) multiple pairwise registrations, and ii) fusion of the deformed segmentation masks towards labeling objects of interest. In this paper we propose an approach for integrated volume segmentation through multi-atlas registration. To tackle this problem, we opt for a graphical model where registration and segmentation nodes are coupled. The aim is to recover simultaneously all atlas deformations along with selection masks quantifying the participation of each atlas per segmentation voxel. The above is modeled using a pairwise graphical model where deformation and segmentation variables are modeled explicitly. A sequential optimization relaxation is proposed for efficient inference. Promising performance is reported on the IBSR dataset when comparing to majority voting and local appearance-based weighted voting.