A method of transmarking a watermarked media signal to adapt the watermark to the robustness and perceptibility constraints of a new environment. This transmarking method detects the first digital watermark in the media signal. It then embeds message information from the first digital watermark into a second digital watermark in the media signal before the media signal undergoes a transformation process. The second digital watermark is adapted to survive the transformation process. A variation of this method detects the first digital watermark in the media signal, converts the media signal to a different format, and embeds message information from the first digital watermark into a second digital watermark in the converted media signal. The second digital watermark is adapted to robustness or perceptibility parameters associated with the new format.