Embodiments of a space-time decoder and methods for decoding Alamouti-encoded signals in high-Doppler environments are generally described herein. Other embodiments may be described and claimed. In some embodiments, soft-symbol outputs are generated from received symbols, a channel rate-of-change, and channel coefficients. Maximum-likelihood decoding may be performed to generate hard-symbol outputs from the soft-symbol outputs.