Our proposed work is apply stenography algorithm in a video stream. In previous stenography methods spatial or transformed domain is used for data hiding. But in proposed method we are using compressed video to hide the secret data; we use motion vectors to encode and reconstruct both the forward predictive (P)-frame and bidirectional (B)-frames in compress video. Motion vectors are calculated using macro block prediction error, which is different from the approaches based on the motion vector attributes such as the magnitude and phase angle, etc. A greedy adaptive threshold is searched for every frame to achieve robustness while maintaining a low prediction error level. Secrete Message bits are replaced with the least significant bits of motion vectors. This algorithm was tested on different types of videos. Based on the aforementioned criteria, the proposed method is found to perform well and is compared to a motion vector attributebased method from the literature.