A novel scheme for non-rigid video object tracking using segment-based object candidates is proposed in this paper. Rather than using a conventional bounding box, the tracker is based on segments and considers the target object to be a combination of segments, where the hierarchical hue-saturation-value histogram is extracted as a feature. The objectness method is employed and integrated into the tracker to generate candidates for a similarity measure. Moreover, segment-based motion weights are introduced to give higher weights to candidates with motion consistency. A confidence-collecting scheme is proposed for similar candidates. To validate our method, experiments were conducted using several image sequences with different non-rigid challenges. The experimental results show that the proposed scheme can achieve better performance than other state-of-the-art methods.