Frequency-domain decision-feedback equalizer (FD-DFE) is a promising alternative to orthogonal frequency-division multiplex (OFDM) for high-speed wireless transmission. In this paper, we present a systematic two-stage framework to derive its analytical error performance in the presence of error propagation effect. First, under the perfect feedback assumption, the pseudo signal-to-noise ratio of the novel FD-DFE receiver with a successive feedback tap assignment algorithm is derived. Using Gaussian approximation (GA), a lower-bound bit-error-rate (BER) performance is also obtained. Then, the error propagation problem is modeled as a vector Markov chain, and we derive the state transition probability matrix, limiting-state probabilities, and the final analytic BER performance. For sparse channel, the number of states and complexity of error can be greatly reduced. To verify the analysis, we consider a practical scenario of 802.16d SCa-PHY, where the FD-DFE receiver under the SUI-5 channel is evaluated. It is shown that the theoretical performance curves coincide well with the Monte-Carlo simulation results.