The latest video coding standard High Efficiency Video Coding (HEVC) achieves about a 50% bit-rate reduction compared with H.264/AVC under the same perceptual video quality. For intra coding, a coding unit (CU) is recursively divided into a quadtree-based structure from the largest CU 64 × 64 to the smallest CU 8 × 8. Also, up to 35 intra-prediction modes are allowed. These two techniques improve the intra-coding performance significantly. However, the encoding complexity increases several times compared with H.264/AVC intra coding. In this paper, fast intra-mode decision and CU size decision are proposed to reduce the complexity of HEVC intra coding while maintaining the rate-distortion (RD) performance. For fast intra-mode decision, a gradient-based method is proposed to reduce the candidate modes for rough mode decision and RD optimization. For fast CU size decision, the homogenous CUs are early terminated first. Then two linear support vector machines that employ the depth difference and HAD cost ratio (and RD cost ratio) as features are proposed to perform the decisions of early CU split and early CU termination for the rest of the CUs. Experimental results show that the proposed fast intra-coding algorithm achieves about a 54% encoding time reduction on average with only a 0.7% BD-rate increase for the HEVC reference software HM 14.0 under all-intra configuration.