A fast CU size decision algorithm is proposed for High Efficiency Video Coding (HEVC) intra prediction in this paper. Prediction unit (PU) is decided by analyzing the threshold of judgment, the complexity of the algorithm is increased if the threshold is too big, and the quality of the image is seriously damaged if the threshold is too small. The robustness of the algorithm would be destroyed if the threshold was not selected well. The robustness is enhanced by deciding the threshold with the statistic of rate-distortion costs and the Minimum Mean Squared Error Estimators (MMSE) simultaneously. Experimental results show that the encoding speed can be evidently improved, the encoding time is reduced by 103% on average, while the BD-Rate gain is only 4.6%, and the image quality is equally perceptual.