This paper addresses the problem of training sequence design for multiple-antenna transmissions over quasi-static frequency-selective channels. As performance metric for channel estimation, mean square error is adopted. To achieve the minimum mean square error, the training sequences transmitted from the multiple antennas must have impulse-like auto-correlation and zero cross-correlation. We reduce the problem of designing multiple training sequences to the much easier and well-understood problem of designing a single training sequence with impulse-like auto-correlation. To this end, we propose to encode the training sequences with a space-time code, that may be the same or different from the space-time code that encodes the information symbols. Designing one instead of multiple training sequences reduces the search space significantly and simplifies the construction of optimal or suboptimal training sequences.