While numerous algorithms have been proposed for object tracking with demonstrated success, it remains a challenging problem for a tracker to handle large appearance change due to factors such as scale, motion, shape deformation, and occlusion. One of the main reasons is the lack of effective image representation schemes to account for appearance variation. Most of the trackers use high-level appearance structure or low-level cues for representing and matching target objects. In this paper, we propose a tracking method from the perspective of midlevel vision with structural information captured in superpixels. We present a discriminative appearance model based on superpixels, thereby facilitating a tracker to distinguish the target and the background with midlevel cues. The tracking task is then formulated by computing a target-background confidence map, and obtaining the best candidate by maximum a posterior estimate. Experimental results demonstrate that our tracker is able to handle heavy occlusion and recover from drifts. In conjunction with online update, the proposed algorithm is shown to perform favorably against existing methods for object tracking. Furthermore, the proposed algorithm facilitates foreground and background segmentation during tracking.