The existence of huge volumes of near-duplicate videos shows a rising demand on effective near-duplicate video retrieval technique in copyright violation and search result re-ranking. In this paper, Kernel Partial Least Squares (KPLS) is used to find strong information correlation in near-duplicate videos. Furthermore, to solve the problem of “curse of kernelization” when querying a large-scale video database, we propose a Toeplitz Kernel Partial Least Squares method. The Toeplitz matrix multiplication can be implemented by the Fast Fourier Transform (FFT) to accelerate the computation. Extensive experiments on the widely used CC_WEB_VIDEO dataset demonstrate that the proposed approach exhibits superior performance of near-duplicate video retrieval (NDVR) over state-of-the-art methods, such as BCS, SE, SSBelt and CCA, achieving a mean average precision (MAP) score of 0.9665.