Estimating a signal which is buried inside colored noise is challenging since significant amount of the noise frequencies with considerable or higher power reside in the same band as that of the desired waveform. In this paper, an optimization- and Karhunen-Loeve Transform (KLT)- based approach has been investigated and tested to estimate the latencies of single-trial visual evoked potentials (VEPs) which are highly corrupted by colored electroencephalogram (EEG) noise. The normal voltage level for a VEP is around 10 μV and the background EEG is in the proximity of 100 μV, producing a signal-to-noise ratio (SNR) in the range of -10 dB. The studied method devices an explicit pre-whitening scheme aimed at producing a symmetric basis matrix, which eventually generates a unitary eigenvector matrix that simultaneously diagonalizes both the wanted signal and noise correlation matrices. The absolute diagonalization ensures full decorrelation of the observed signal, and permits the segregation of the transformed signal space into the "signal plus noise subspace" and "noise only subspace." The performance of the KLT-based method in estimating VEP latencies has been assessed using comprehensively and realistically simulated data at SNR ranging from 0 to -10 dB, and real patient data gathered in a hospital. The technique produces reasonably high success rates, high accuracies and precisions, and narrow standard deviations in both experiments. © EURASIP, 2010.