Apparatus, devices, systems, methods, and articles of manufacture are disclosed for watermarking with phase shifting. An example watermark encoding apparatus includes memory, machine readable instructions, and processor circuitry to execute the instructions to select a plurality of frequencies for encoding a watermark symbol, apply a phase shift pattern to the plurality of frequencies, the phase shift pattern based on a phase reference, and embed in the plurality of frequencies the applied phase shift pattern in a media signal to encode the watermark symbol in the a media signal, and embed the phase reference into the media signal.