Visual tracking under illumination changes is a challenging task for numerous computer vision applications. We propose a robust and efficient tracking algorithm based on maximum color difference histogram (MCDH) and a well-designed min-max-ratio (MMR) similarity metric. Appearance model is essential to the tracker’s robustness under illumination changes. We propose a new feature descriptor MCDH, calculated by exploiting the maximum color difference information within the eight-neighborhood of each pixel in the object region, to build the object appearance model. Unlike the traditional histogram-based algorithms, the MCDH is efficiently extracted by employing the local integral histogram which is propagated in a specially designed local image region. The similarity metric plays an important role on accurately locating the target. However, the existing metrics are not suitable for comparisons of MCDHs due to many zero-valued bins in MCDH. Therefore, we propose a new MMR metric, defined as the average ratio between the minimum and maximum of a MCDH bin pair. The combination of proposed components enables the tracker to be robust to illumination changes with high computational efficiency. Experiments demonstrate superior performance of the proposed tracking algorithm compared with 10 state-of-art tracking methods when illumination varies.