The exhaustive block partition search process in high efficiency video coding (HEVC) imposes a very high computational complexity on test module of HEVC encoder (HM). A fast coding unit (CU) depth algorithm using the spatio-temporal correlation of the depth information to fasten the search process is proposed. The depth of the coding tree unit (CTU) is predicted first by using the depth information of the spatio-temporal neighbor CTUs. Then, the depth information of the adjacent CU is incorporated to skip some specific depths when encoding the sub-CTU. As compared with the original HM encoder, experimental results show that the proposed algorithm can save more than 20% encoding time on average for intra-only, low-delay, low-delay P slices, and random access cases with almost the same rate-distortion performance.