This paper explores ways to incorporate effective teaching methods in computer-aided pronunciation training (CAPT) programs to help second language learners acquire Mandarin lexical tones. It is hypothesized that exaggerated stimuli might help learners to identify relevant acoustic cues, varied stimuli might help them build robust classifications, and an adaptive training program would provide a platform for efficient learning. We conducted an experiment to compare four training modules: (1) a control group with no tone training, (2) training with similar stimuli, (3) training with varied stimuli in random order, and (4) training with varied stimuli through an adaptive training program. The adaptive group had the best performance: students showed an average 8.2 points improvement on a 100-point scale, or 32% error reduction, after two and a half hours of training. The experiment results also show that while varied input benefited most students, some students may have been confused by such input. Adaptive training effectively alleviated such confusion. The methodology developed here can apply straightforwardly to the teaching of speech sounds in other languages.