3D extension of High Efficiency Video Coding (3D-HEVC) is the newest international standard for 3D video coding. Compared to conventional HEVC, the encoding materials consist of multi-view color textures and associated depth maps. However, the advanced techniques enhance the coding efficiency at the cost of the computation complexity and time consumption. In this paper, we propose an early termination algorithm to speed-up the encoding procedure. With the complexity check by total sum of squares (TSS) and the RD-cost criterion, we effectively accelerate the depth intra coding of 3D-HEVC and maintain the video quality. The experimental results show that both of the time-saving and the BD-BR performance of our method outperform previous works.