Multi-atlas segmentation has been widely applied to the analysis of brain MR images. However, the state-of-the-art techniques in multi-atlas segmentation, including both patch-based and learning-based methods, are strongly dependent on the pairwise registration or exhibit huge spatial inconsistency. The paper proposes a new segmentation framework based on supervoxels to solve the existing challenges of previous methods. The supervoxel is an aggregation of voxels with similar attributes, which can be used to replace the voxel grid. By formulating the segmentation as a tissue labeling problem associated with a maximum-a-posteriori inference in Markov random field, the problem is solved via a graphical model with supervoxels being considered as the nodes. In addition, a dense labeling scheme is developed to refine the supervoxel labeling results, and the spatial consistency is incorporated in the proposed method. The proposed approach is robust to the pairwise registration errors and of high computational efficiency. Extensive experimental evaluations on three publically available brain MR datasets demonstrate the effectiveness and superior performance of the proposed approach.