Aiming at the high computational complexity of recursive quad-tree partition of Coding Unit (CU) in High Efficiency Video Coding (HEVC), an improved fast CU partition algorithm of HEVC was proposed. Firstly, based on the temporal-spatial correlation among neighboring CUs, the best partition structure from the co-located position of the previous frames is extracted to predict the depth of partition CU. Secondly, a fast CU partitioning structure decision algorithms are improved to reduce traversal of Coding Tree Unit (CTU) quad-tree structure. It means that the traverse operation begins from the half depths of CU partitions structure, and whether to early termination of traversal is judged before each step traversal. We compare to baseline works in HM 15.0, showing the proposed algorithm can reduce the encoding time by 55.4% while improving the coding performance and improve the coding efficiency of HEVC compared with the quad-tree recursive traversal algorithm.