The intra prediction in HEVC exploits the new techniques, such as the tree coding structure and up to 35 intra prediction modes, etc., to achieve high coding efficiency but incur heavy computational complexity as well. To reduce the computational complexity, a novel fast mode decision algorithm for intra prediction in HEVC is proposed in this paper. In the proposed algorithm, by using the texture characteristic of the current prediction unit (PU) and the similarity between neighboring PUs, the proposed rough and refine decision schemes are sequentially utilized to reduce the number of candidate prediction modes required for checking so that the computational complexity can be greatly saved. Experimental results have demonstrated that the proposed algorithm can reduce, on average, 25% computational complexity with negligible loss of coding efficiency, compared with the fast intra mode decision method implemented in HEVC reference software.