We propose a novel algorithm called graph-shifts for performing image segmentation and labeling. This algorithm makes use of a dynamic hierarchical representation of the image. This representation allows each iteration of the algorithm to make both small and large changes in the segmentation, similar to PDE and split-and-merge methods, respectively. In particular, at each iteration we are able to rapidly compute and select the optimal change to be performed. We apply graph-shifts to the task of segmenting sub cortical brain structures. First we formalize this task as energy function minimization where the energy terms are learned from a training set of labeled images. Then we apply the graph-shifts algorithm. We show that the labeling results are comparable in quantitative accuracy to other approaches but are obtained considerably faster: by orders of magnitude (roughly one minute). We also quantitatively demonstrate robustness to initialization and avoidance of local minima in which conventional boundary PDE methods fall.