Abstract: As it is crucial for object tracking to establish a robust appearance model, an algorithm for object tracking based on incremental non-negative matrix factorization is presented.Firstly, resorting to a transition probability model, a set of image patches are predicated as candidates for object image in the current frame, and then non-negative matrix factorization is used to obtain the low-dimensional coordinate vectors of the image patches.With the coordinate vectors, the associations between image patches and object image in the previous frame are evaluated, and the image sample with the maximum association is regarded as the image region of the moving object in the current frame.Finally, the subspace of object images is updated incrementally, thus the efficiency is improved in addition to a constant storage requirement.Experimental results show that our algorithm is able to adapt to variations in appearance of objects well, and it can track objects more steadily.