Purpose: We present a segmentation method that maximizes regional probabilities enclosed by coupled surfaces using an Optimal Surface Graph (OSG) cut approach. This OSG cut determines the globally optimal solution given a graph constructed around an initial surface. While most methods for vessel wall segmentation only use edge information, we show that maximizing regional probabilities using an OSG improves the segmentation results. We applied this to automatically segment the vessel wall of the carotid artery in magnetic resonance images. Methods: First, voxel-wise regional probability maps were obtained using a Support Vector Machine classifier trained on local image features. Then, the OSG segments the regions which maximizes the regional probabilities considering smoothness and topological constraints. Results: The method was evaluated on 49 carotid arteries from 30 subjects. The proposed method shows good accuracy with a Dice wall overlap of 74.1 ± 4.3%, and significantly outperforms a published method based on an OSG using only surface information, the obtained segmentations using voxel-wise classification alone, and another published artery wall segmentation method based on a deformable surface model. Intraclass correlations (ICC) with manually measured lumen and wall volumes were similar to those obtained between observers. Finally, we show a good reproducibility of the method with ICC = 0.86 between the volumes measured in scans repeated within a short time interval. Conclusions: In this work, a new segmentation method that uses both an OSG and regional probabilities is presented. The method shows good segmentations of the carotid artery in MRI and outperformed another segmentation method that uses OSG and edge information and the voxel-wise segmentation using the probability maps.