In accordance with an embodiment, a method of watermarking encoded video frames includes electronically receiving a bitstream comprising a plurality of encoded video frames that are divided into a plurality of macro-blocks, determining macro-block dependencies based on prediction information in the received bitstream, determining a set of macro-blocks having a minimal number of macro-block dependencies, and embedding a watermark in a plurality of macro-blocks selected from the set of macro-blocks having the minimal number of macro-block dependencies.