Nowadays, verifying the integrity of digital videos is significant especially for applications about multimedia communication. In video forensics, detection of double compression can be treated as the first step to analyze whether a suspicious video undergoes any tampering operations. In the last decade, numerous detection methods have been proposed to address this issue, but most existing methods design a universal detector which is hard to handle various recompression settings efficiently. In this work, we found that the statistics of different Coding Unit (CU) types have dissimilar properties when original videos are recompressed by the increased and decreased bit rates. It motivates us to propose a two-stage cascaded detection scheme for double HEVC compression based on temporal inconsistency to overcome limitations of existing methods. For a given video, CU information maps are extracted from each short-time video clip using our proposed value mapping strategy. In the first detection stage, a compact feature is extracted based on the distribution of different CU types and Kullback–Leibler divergence between temporally adjacent frames. This detection feature is fed into the Support Vector Machine classifier to identify abnormal frames with the increased bit rate. In the second stage, a shallow convolutional neural network equipped with dense connections is designed carefully to learn robust spatiotemporal representations, which can identify abnormal frames with the decreased bit rate whose forensic traces are less detectable. In experiments, the proposed method can achieve more promising detection accuracy compared with several state-of-the-art methods under various coding parameter settings, especially when the original video is recompressed with a low quality (e.g., more than 8%).