An object tracking algorithm with multi-bandwidth and adaptive over-relaxed accelerated convergence was proposed to avoid the local probability mode in a Mean Shift tracking process. Firstly, a monotonically decreasing sequence of bandwidths was obtained according to the object scale. At the first bandwidth, a maximum probability could be found with the Mean Shift, and the next iteration loop started at the previous convergence location. Finally, the best density mode was obtained at the optimal bandwidth. In the convergence process, the compactness of the local probability mode was avoided with the smoothing effect of the large bandwidth, and the precise position of the object could be found with the optimal bandwidth, which was similar to the object scale. To speed up the convergence, an over-relaxed strategy was introduced to enlarge the step size. Under the convergence rule, the correlation coefficient was used to adjust the learning rate adaptively. The experimental results prove that the proposed tracker with multi-bandwidth Mean Shift is robust in high-speed object tracking, and performs well in occlusions. The experimental results also show that the adaptive over-relaxed strategy reduces the convergence iterations by 30%-70%.