Steganography is the art of secret communication and steganalysis is the art of detecting the hidden messages embedded in digital media covers. One of the covers that is gaining interest in the field is video. Presently, the global IP video traffic forms the major part of all consumer Internet traffic. It is also gaining attention in the field of digital forensics and homeland security in which threats of covert communications hold serious consequences. Thus, steganography technicians will prefer video to other types of covers like audio files, still images or texts. Moreover, video steganography will be of more interest because it provides more concealing capacity. Contrariwise, investigation in video steganalysis methods does not seem to follow the momentum even if law enforcement agencies and governments around the world support and encourage investigation in this field. In this paper, we review the most important methods used so far in video steganalysis and sketch the future trends. To the best of our knowledge this is the most comprehensive review of video steganalysis produced so far.