In this paper we propose an approach for integrated volume segmentation and multi-atlas registration. The aim is to recover simultaneously all atlas deformations along with a segmentation mask that imposes consistency between their deformed segmentation maps. This is modeled through a pairwise graphical model where deformation variables are coupled with segmentation ones. Optimization via dual decomposition is used to recover the optimal solution of the method. Promising results on the IBSR dataset demonstrate the potential of our method where improvement is obtained when comparing to the post-registration label fusion.