In this paper, we propose a constrained graph labeling algorithm for visual tracking where nodes denote superpixels and edges encode the underlying spatial, temporal, and appearance fitness constraints. First, the spatial smoothness constraint, based on a transductive learning method, is enforced to leverage the latent manifold structure in feature space by investigating unlabeled superpixels in the current frame. Second, the appearance fitness constraint, which measures the probability of a superpixel being contained in the target region, is developed to incrementally induce a long-term appearance model. Third, the temporal smoothness constraint is proposed to construct a short-term appearance model of the target, which handles the drastic appearance change between consecutive frames. All these three constraints are incorporated in the proposed graph labeling algorithm such that induction and transduction, short- and long-term appearance models are combined, respectively. The foreground regions inferred by the proposed graph labeling method are used to guide the tracking process. Tracking results, in turn, facilitate more accurate online update by filtering out potential contaminated training samples. Both quantitative and qualitative evaluations on challenging tracking data sets show that the proposed constrained tracking algorithm performs favorably against the state-of-the-art methods.