With the development of video coding technology, high-efficiency video coding (HEVC) has become a promising alternative, compared with the previous coding standards, for example, H.264. In general, H.264 to HEVC transcoding can be accomplished by fully H.264 decoding and fully HEVC encoding, which suffers from considerable time consumption on the brute-force search of the HEVC coding tree unit (CTU) partition for rate-distortion optimization (RDO). In this paper, we propose a deep learning method to predict the HEVC CTU partition, instead of the brute-force RDO search, for H.264 to HEVC transcoding. First, we build a large-scale H.264 to HEVC transcoding database. Second, we investigate the correlation between the HEVC CTU partition and H.264 features, and analyze both temporal and spatial-temporal similarities of the CTU partition across video frames. Third, we propose a deep learning architecture of a hierarchical long short-term memory (H-LSTM) network to predict the CTU partition of HEVC. Then, the brute-force RDO search of the CTU partition is replaced by the H-LSTM prediction such that the computational time can be significantly reduced for fast H.264 to HEVC transcoding. Finally, the experimental results verify that the proposed H-LSTM method can achieve a better tradeoff between coding efficiency and complexity, compared to the state-of-the-art H.264 to HEVC transcoding methods.