This paper presents a novel multiple-level patch-based approach for object tracking using Modified Local Binary Pattern (MLBP) histograms. The initial template is divided into overlapping rectangular patches, and each of these patches is tracked independently by finding the most similar match within a search region. Every patch votes on the possible locations of the object in the current frame, by comparing its MLBP histogram with the correspondence in the target frame. To reduce the individual tracking error of a given patch due to partial occlusions, the idea of multiple-level patch partitioning is further developed. And the similarity between template and target object is compared patch-by-patch, level-by-level. The comparison starts from the highest level and progressively feeds to the lowest level through a median operation. The proposed algorithm provides additional robustness and effectiveness in several ways. First, the spatial relationship among patches is improved by this overlapping partitioning manner. Second, by introducing MLBP operator, the tracking accuracy is significantly improved. Third, the median operation utilized in the multiple-level vote-combining process provides additional robustness with respect to outliers resulting from occluded patches and pose changes. The proposed method is evaluated using both face and pedestrian sequences, and comparison is made w.r.t. several state-of-the-art tracking algorithms. Experimental results show that the proposed method significantly outperforms in case of occlusions and pose changes. Besides, the tracking in case of scale changes additionally proves the effectiveness and efficiency of the proposed method.