An adaptive Karhunen-Loeve transform (KLT) tracking-based algorithm is proposed for enhancement of speech degraded by colored additive interference. This algorithm decomposes noisy speech into its components along the axes of a KLT-based vector space of clean speech. It is observed that the noise energy is disparately distributed along each eigenvector. These energies are obtained from noise samples gathered from silence intervals between speech samples. To obtain these silence intervals, we proposed an efficient voice activity detector based on outputs of the principle component eigenfilter; the greatest eigenvalue of speech KLT. Enhancement is performed by modifying each KLT component due to its noise and clean speech energies. The objective is to minimize the produced distortion when residual noise power is limited to a specific level. At the end, the inverse KLT is performed and an estimation of the clean signal is synthesized. Our listening tests indicated that 71% of our subjects preferred the enhanced speech by the above method over former methods of enhancement of speech degraded by computer generated white Gaussian noise. Our method was preferred by 80% of our subjects when we processed real samples of noisy speech gathered from various environments.