A novel robust video hashing scheme is proposed in this paper. Unlike most existing robust video hashing algorithms, the proposed video hash is generated based on the motion vectors instead of the image textures in the video stream. Therefore, neither full decoding of the video stream nor complex computation of pixel values is required. Based on analysis of motion vector properties regarding their suitability for robust hashing, an improved feature extraction mechanism is proposed and several optimization mechanisms are introduced in order to achieve better robustness and discriminability. The proposed hashing scheme is evaluated by a large and modern video data set and the experimental results demonstrate the excellent performance of the proposed hashing algorithm, which is comparable or even better than the complicated texture-based approaches.