Image segmentation is, in general, an ill-posed problem and additional constraints need to be imposed in order to achieve the desired segmentation result. While segmenting organs in medical images, which is the topic of this paper, a significant amount of prior knowledge about the shape, appearance, and location of the organs is available that can be used to constrain the solution space of the segmentation problem. Among the various types of prior information, the incorporation of prior information about shape, in particular, is very challenging. In this paper, we present an explicit shape-constrained MAP-MRFbased contour evolution method for the segmentation of organs in 2D medical images. Specifically, we represent the segmentation contour explicitly as a chain of control points. We then cast the segmentation problem as a contour evolution problem, wherein the evolution of the contour is performed by iteratively solving a MAP-MRF labeling problem. The evolution of the contour is governed by three types of prior information, namely: (i) appearance prior, (ii) boundary-edgeness prior, and (iii) shape prior, each of which are incorporated as clique potentials into the MAP-MRF problem. We use the master-slave dual decomposition framework to solve the MAP-MRF labeling problem in each iteration. In our experiments, we demonstrate the application of the proposed method to the challenging problem of heart segmentation in non-contrast computed tomography data.