Digital video watermarking has attracted a great deal of research interest in the past few years in applications such as digital fingerprinting and owner identification. The H.264/AVC (advanced video coding) standard is the latest and most advanced video coding standard, but to this date, very few watermarking schemes have been designed for it. This is mainly due to its complexity and compression efficiency, which present a major challenge for any video watermarking approach. We developed a new, quantization-based video watermarking scheme that is designed to work with H.264/AVC. We propose a locally adaptive, rate-distortion optimized watermark that is inserted in the transform coefficients of the macro blocks. We use a unique perceptual mask in order to control the levels of spatial and temporal distortion. Our scheme is designed with a built-in bit allocation mechanism that ensures optimum distribution of watermark bits between different macro blocks. Our watermark offers constant robustness to H.264 video compression at different bit rates, without significantly affecting the overall bit rate and quality of the video stream. Experimental results show that our scheme outperforms existing watermarking methods under compression, transcoding, filtering, scaling, rotation, and collusion attacks.