The traditional target tracking algorithms based on compressive sensing uses color video sequence. It is easily affected by rotation, occlusion and illumination. Thus it has poor robustness in complex environment. In order to obtain stable tracking results, this paper proposed a novel face detection and tracking algorithm using compressive sensing based on depth information. Firstly, we identify the position of face in the initial depth map automatically using the improved centroids segmentation algorithm. Secondly, we calculate the mean curvature graph with the depth map. Thirdly, the compression features are extracted based on the mean curvature graph. Finally, by compression and dimension reduction, the feature template is updated and the best postion of face is estimated in the neighborhood space based on the mean curvature graph. The experiment results demonstrate that by combining the depth information of human face and the compressive sensing feature, the proposed algorithm has better robustness dealing with problems of rotation, illumination and occlusion.