In this paper we propose a general framework for video-based object segmentation using a new spatio-temporal Markov Random Field (MRF) model. Video-based object segmentation has the potential to improve the performance of static image segmentation by fusing in- formation over the temporal scale. Built upon a spatio-temporal MRF model, our method offers three advantages in a unified framework. First, our model is defined on a flexible graph structure induced by the local motion information instead of the regular 3D grid, allowing the model nodes to be connected to more reliable temporal neighbors. Second, the segmentation task is considered in unison with foreground/background modeling, leading to more accurate appearance models suitable for object segmentation. Third, the inclusion of shape priors as a top-down high- level object constraints as guides for the bottom-up low-level image cues leads to improved segmentation. The object segmentation is solved as an MRF-MAP inference problem by the Loopy Belief Propagation (LBP) algorithm effectively and efficiently. Estimation of the model parameters can be accomplished simultaneously with the inference problem, using an Expectation Maximization (EM) algorithm. In our experiments, we show promising object segmentation results by combining multiple modules in the same framework.