In this paper a new enhancement scheme for highly noise-corrupted data is presented and evaluated. The approach combines the Karhunen- Loève Transform (KLT) and Genetic Algorithms (GAs) in order to enhance noise-corrupted speech. The principle consists of projecting noisy Mel-Frequency Cepstral Coefficients (MFCCs) onto the space generated by the principal axes issued from the KLT analysis and optimized by genetic operators such as crossover and mutations. Results show that the proposed hybrid technique, when included in the front-end of an HTK-based continuous speech recognition system, outperforms that of the conventional recognition process in severe interfering car noise environments. Experiments concern a wide range of Signal-to-Noise-Ratios (SNRs) varying from 16 dB to -4 dB, and use a noisy version of the TIMIT speech database.