Human tracking is an important vision task in video surveillance and perceptual human-computer interfaces. This paper presents a novel algorithm for region-based human tracking using color and depth features. We propose an adaptive autoregressive logarithmic search (ARLS) to estimate the target position, and use depth information to further reduce the false alarm rate. The new ARLS algorithm is evaluated on a color and depth (RGBD) video dataset acquired with the Kinect sensor. The dataset contains various real-world scenarios with illumination and speed variations, and partial occlusion. The experimental results show that the ARLS algorithm is able to handle difficult tracking scenarios; it achieves a tracking accuracy of 91.26% on the test dataset. The proposed algorithm is compared with two tracking algorithms, namely the particle filtering and a modified logarithmic search algorithm. © 2012 IEEE.