Differentiating anomalous audio document (Stego audio) from pure audio document (cover audio) is difficult and tedious. Steganalytic techniques strive to detect whether an audio contains a hidden message or not. This paper presents a genetic algorithm (GA) based approach to audio steganalysis, and the software implementation of the approach. The basic idea is that, the various audio quality metrics calculated on cover audio signals and on stego-audio signals vis-à-vis their denoised versions, are statistically different. GA is employed to derive a set of classification rules from audio data using these audio quality metrics, and fitness function is used to judge the quality of each rule. The generated rules are then used to detect or classify the audio documents in a real-time environment. Unlike most existing GA-based approaches, because of the simple representation of rules and the effective fitness function, the proposed method is easier to implement while providing the flexibility to generally detect any new steganography technique. The implementation of the GA based audio steganalyzer relies on the choice of these audio quality metrics and the construction of a two-class classifier, which will discriminate between the adulterated and the untouched audio samples. Experimental results show that the proposed technique provides promising detection rates. ©2006 IEEE.