In this work, boosting the efficiency of Mean-Shift Tracking using random sampling is proposed. We obtained the surprising result thatmean-shift tracking requires only very few samples. Our experiments demonstrate that robust tracking can be achieved with as few as even 5 random samples from the image of the object. As the computational complexity is considerably reduced and becomes independent of object size, the processor can be used to handle other processing tasks while tracking. It is demonstrated that random sampling significantly reduces the processing time by two orders of magnitude for typical object sizes. Additionally, with random sampling, we propose a new optimal on-line feature selection algorithm for object tracking which maximizes a similarity measure for the weights of the RGB channels. It selects the weights of the RGB channels which discriminate the object and the background the most using Steepest Descent. Moreover, the spatial distribution of pixels representing the object is estimated for spatial weighting.Arbitrary spatial weighting is incorporated into Mean-Shift Tracking to represent objects with arbitrary or changing shapes by picking up non-uniform random samples. Experimental results demonstrate that our tracker with online feature selection and arbitrary spatial weighting outperforms the original mean-shift tracker with improved computational efficiency and tracking accuracy.