Steganalysis, the method to detect steganographically embedded hidden messages in digital data, has received an increasing interest in recent years. Although significant research efforts have been devoted to develop steganalysis techniques for still-images, video steganalysis remains largely an explored area. In this paper, we investigate how the temporal correlation in the neighbouring frames of a video sequence can be exploited to improve the video steganalysis performance. The reported experimental results indicate that significant improvement in the detection rate, as high as 30%, can be achieved by exploiting the temporal correlation.