The segmentation of brain magnetic resonance imaging is a difficult task, essential to several applications in neuroscience. Atlas-based methods are often employed for this task since they provide prior information in the form of labels, without the manual intervention of a trained technician. In this paper, we present a novel and efficient atlas-based segmentation method based on random walks. Unlike most atlas-based approaches, our method combines the registration and label propagation steps in a single efficient framework. Moreover, this method does not depend on a specific deformation model, making it more robust to complex transformations not captured by such models. Experiments on benchmark brain MRI data show the usefulness and efficiency of our method.