High Efﬁciency Video Coding (HEVC), the latest video coding standard, achieves signiﬁcantly better compression performance than the previous coding standards, especially for high resolution (2K, 4K, etc.) video coding. Intra frame coding adopts a ﬂexible quad-tree coding block structure to get the best coding unit partition, which results in extremely high computational complexity. In this paper, a fast depth decision algorithm with enlarged block sizes is proposed to speed up HEVC intra coding for 4K Ultra-HD video. Firstly, sizes of Coding Unit (CU), Prediction Unit (PU) and Transform Unit (TU) are enlarged in the modiﬁed Coding Tree Unit structure to reduce coding complexity. Then, gradient information of an image is exploited for early CU termination to optimize CU partition process. Experimental results of several 4K video sequences show that the proposed algorithm can achieve about 56% encoding time reduction compared to HEVC reference software while maintaining the same encoding performance.