This paper addresses the problem of soft equalization for space-time-coded transmissions over frequency-selective fading channels. The structure of the space-time code is embedded in the channel impulse response for efficient joint equalization and decoding. The proposed equalization/decoding approach uses a prefilter to concentrate the effective channel power in a small number of taps followed by a reduced-complexity maximum a posteriori probability (MAP) equalizer/decoder to produce soft decisions. The prefilter introduces residual intersymbol interference which degrades the performance of MAP when applied to the trellis of the shortened channel. However, the shape of the overall shortened channel impulse response allows the M-algorithm to approximate the prefiltered MAP performance with a small number of states. Based on this general framework, we investigate several enhancements such as using different prefilters for the forward and backward recursions, concatenating two trellis steps during decoding, and temporal oversampling. The performance is evaluated through simulations over the EDGE typical urban channel.