Multi-atlas label fusion methods have gained popularity in a variety of segmentation tasks given their attractive performance. Graph-based segmentation methods are widely used given their global optimality guarantee. We propose a novel approach, GOLF, that combines the strengths of these two approaches. GOLF incorporates shape priors to the label-fusion problem and provides a globally optimal solution even for the multi-label scenario, while also leveraging the highly accurate posterior maps from a multi-atlas label fusion approach. We demonstrate GOLF for the joint segmentation of the left and right pairs of caudate, putamen, globus pallidus and nucleus accumbens. Compared to the FreeSurfer and FIRST approaches, GOLF is significantly more accurate on all reported indices for all 8 structures. We also present comparisons to a multi-atlas approach, which reveals further insights on the contributions of the different components of the proposed framework.