Abstract High Efficiency Video Coding (HEVC) is a state-of-the-art video compression standard which improves coding efficiency significantly compared with the previous coding standard, H.264/AVC. In the HEVC standard, novel technologies consuming massive computational power are adopted, such as quad-tree-based coding unit (CU) partitioning. Although an HEVC encoder can efficiently compress various video sequences, the computational complexity of an exhaustive search has become a critical problem in HEVC encoder implementation. In this paper, we propose a fast algorithm for the CU partitioning process of the HEVC encoder using machine learning methods. A complexity measure based on the Sobel operator and rate-distortion costs are defined as features for our algorithm. A CU size can be determined early by employing Fisher’s linear discriminant analysis and the k-nearest neighbors classifier. The statistical data used for the proposed algorithm is updated by adaptive online learning phase. The experimental results show that the proposed algorithm can reduce encoding time by approximately 54.0% with a 0.68% Bjontegaard-Delta bit-rate increase.