Intra coding has been significantly improved in HEVC over H.264/AVC with quad-tree based coding unit (CU) structure from size 64×64 to 8×8 and more prediction modes. However, these techniques cause a dramatic increase in computational complexity. In this paper, a novel intra coding algorithm is proposed consists of perceptual CU size decision algorithm and fast intra prediction mode decision algorithm. Firstly, based on the visual saliency detection, an adaptive and perceptual CU size decision method is proposed to alleviate intra encoding complexity. Furthermore, a fast intra prediction mode decision algorithm with step halving rough mode decision method is presented to selectively check the potential modes and effectively reduce the complexity of computation. Experimental results show that our proposed method reduces the computational complexity of the current HM to about 54.18% in encoding time with only 0.36% increases in BD rate and reasonable peak signal-to-noise ratio losses.