This paper addresses the problem of segmentation of moving objects in image sequences, which is of key importance in content-based applications. We transform the problem into a graph labeling problem over a region adjacency graph (RAG), by introducing a Markov random field (MRF) model based on spatio-temporal information. The initial partitionis obtained by a fast, color-based watershed segmentation. The motion of each region is estimated and validated in a hierarchical framework. A dynamic memory, based on object tracking, is incorporated into the segmentation process to maintain temporal coherence. The performance of the algorithm is evaluated on several real-world image sequences.