In this manuscript, we focus on the problem of soft-output detection of spectrally efficient frequency division multiplexing in the presence of frequency-selective fading channels. A novel detection algorithm, resulting from a message passing approach to the considered problem and not requiring matrix inversions nor spectral decompositions, is devised. Our approach is based on a novel scheduling criterion applied to the Forney-style factor graph representation of the approximate maximum likelihood detection problem. Our numerical results evidence that the proposed algorithm outperforms, in terms of achievable rates and communication performance, other detectors available in the technical literature at the price of higher computational complexity and sheds new light on the trade-off between spectral efficiency and detection complexity in a communication system employing spectrally efficient frequency division multiplexing.