Error propagation phenomena is the major drawback for existing hard-decision feedback turbo equalizers. In this paper, we propose a new soft-decision feedback equalizer (SDFE) suitable for multilevel modulation systems employing turbo equalization. The proposed SDFE offers a low computational complexity growing only linearly with the number of equalizer coefficients, as opposed to the quadratic complexity of MMSE-based linear turbo equalizer with time-varying coefficients (Exact-MMSE-LE). The performance and convergence property of the proposed SDFE are analyzed using extrinsic information transfer (EXIT) chart and verified by simulations in a severe intersymbol interference channel set by Proakis. Results show that our approach performs close to Exact-MMSE-LE for BPSK/QPSK modulation. And for 8PSK/16QAM modulations, the proposed SDFE performs much better. It exhibits lower SNR threshold (SNR required for “waterfall” BER) and much faster convergence than Exact-MMSE-LE.