Designing an optimal audio watermarking system is an open difficult issue since its two basic performance measures, i.e., imperceptibility and robustness, are conflicting with each other. So, an optimal audio watermarking scheme needs to optimally balance both imperceptibility and robustness. In order to realize such an optimal watermarking system, by considering the balance as an optimization problem, we propose an optimal audio watermarking scheme using genetic optimization with variable-length mechanism in this paper. The presented genetic optimization procedure can automatically determine optimal embedding parameters for each audio frame of an audio signal. Specially, employed variable-length mechanism can effectively search most suitable positions for watermark embedding, including suitable audio frames and their AC coefficients. By dint of the genetic optimization with variable-length mechanism, proposed audio watermarking scheme can not only guarantee good quality of watermarked audio signal but also effectively improve its robustness. Experimental results show that proposed watermarking scheme has good imperceptibility and high capability against common signal processing and some desynchronization attacks.