Methods and apparatus for performing variable block length watermarking of media are disclosed. Example apparatus include means for evaluating a masking ability of a first audio block; means selecting a first frequency to represent a first code, the means for selecting to (i) select the first frequency selected from a first set of frequencies that are detectable when performing a frequency transformation using a first block length, but are not detectable when performing a frequency transformation using a second block length, and (ii) select a second frequency to represent a second code, the second frequency selected from a second set of frequencies that are detectable when performing a frequency transformation using the second block length; means for synthesizing a first signal having the first frequency with the masking ability of the first audio block; and means for combining the first signal with the first audio block.