This paper examines the problems with temporal synchronization in video watermarking and describes a new method for efficient synchronization and resynchronization. In our method, efficient synchronization is achieved by designing temporal redundancy in the structure of the watermark. Temporal redundancy allows the watermark detector to establish and maintain synchronization without performing extensive search in the watermark key space. Our method does not use synchronization templates that may be subject to attack and increase the visibility of the watermark. Another advantage of our technique is that the watermark structure is video-dependent, which enhances security. The technique is implemented using a spatial domain watermark on uncompressed video and a finite state machine watermark key generator. The implementation illustrates the effectiveness of using temporal redundancy for synchronization, and is shown to be resilient to desynchronization attacks such as frame dropping, frame insertion, local frame transposition, and frame averaging. Our method for synchronization is independent of the embedding method and can be used with a wide class of watermark embedding and detection techniques, including those for other time-varying signals such as digital audio.