IEEE With the increasing popularity of digital video communication, video data hiding has become an active research topic in covert communication and privacy protection. Traditional video data hiding methods often use quantized discrete cosine transform (QDCT) coefficients to carry sufficient payload. However, since QDCT coefficients expose texture features and motion characteristics of the present video frame heavily, data embedding with QDCT coefficients may lead to significant intra-frame distortion and inter-frame distortion drift. To avoid obvious visual artifacts and keep bit-rate within a satisfactory level of the marked video, data embedding in QDCT coefficients should take into account both the intra-frame and inter-frame distortion impacts. It motivates the authors to propose an efficient cost assignment-based video data hiding method in this paper. The proposed cost assignment method aims to accurately evaluate the data embedding distortion. Specifically, the proposed scheme considers intra-frame changes and intra-frame distortion drift, for which the texture and motion changes of frames can be measured. The frame position is also used to reflect a cumulative distortion difference of multiple frames. For data embedding, syndrome-trellis code (STC) is adopted to minimize the overall distortion. Experimental results show that the proposed method significantly outperforms existing works in terms of payload-distortion performance.