In this paper, we propose a On-line kernel-PLS approach to improving both the robustness and accuracy of object tracking which is appropriate for real-time video surveillance. Typical tracking with color histogram matching provides robustness but has insufficient accuracy, because it does not involve spatial information. On the other hand, tracking with pixel-wise matching achieves accurate performance but is not robust against deformation of a target object. To tackle these problems, this paper presents a tracking method that combine histogram-wise matching and pixel-wise template matching via leans a robust object representation by Kernel-PLS analysis and adapts to appearance change of the target. In this paper, we propose a novel On-line Kernel-PLS analysis, for generating a low-dimensional discriminative feature subspace. As object appearance is temporally correlated and likely to repeat over time, we learn and adapt multiple appearance models with On-line Kernel-PLS analysis for robust tracking.