In this paper, a fast watermarking algorithm for the H.264/AVC compressed video using Exponential-Golomb (Exp-Golomb) code words mapping is proposed. During the embedding process, the eligible Exp-Golomb code words of reference frames are first identified, and then the mapping rules between these code words and the watermark bits are established. Watermark embedding is performed by modulating the corresponding Exp-Golomb code words, which is based on the established mapping rules. The watermark information can be extracted directly from the encoded stream without resorting to the original video, and merely requires parsing the Exp-Golomb code from bit stream rather than decoding the video. Experimental results show that the proposed watermarking scheme can effectively embed information with no bit rate increase and almost no quality degradation. The algorithm, however, is fragile and re-encoding at alternate bit rates or transcoding removes the watermark.