We propose an effective approach to make segmentation for objects in videos with an initial input of the object masks in a few frames of the source video. In this method, we cast the segmentation task as a Markov Random Field (MRF) labeling problem. Different from the conventional MRF models, our model uses an additional term of higher-order potential to better propagate the global consistency among frames. The higher-order potential presented in this paper is significant for the proposed method because of its capability to keep the long-range consistency during segmentation. In order to make the MRF energy minimized, we also introduce a smart skill that makes the intractable higher-order potential “invisible” during the optimization so that the problem can be solved simply by applying a standard graph cut algorithm. Besides, the entire process is operated in a bilateral space, where the labeling can be inferred efficiently on the vertices that are sampled regularly from the bilateral grid. The results of a comparison of our method with a number of recently developed methods show that it performs favorably against state-of-the-art algorithms on multiple benchmark data sets in view of accuracy and achieves a much faster runtime performance.