In this paper a new transmit diversity technique is proposed for wireless communications over frequency selective fading channels. The proposed technique utilises orthogonal frequency division multiplexing (OFDM) to transform a frequency selective fading channel into multiple flat fading subchannels on which first space-frequency coding and then additional space-time coding are applied resulting in a space-time-frequency OFDM (STF-OFDM) scheme. This scheme provides a quasi-orthogonal 4 x 4 transmission matrix but relax the constraint on channel fading parameters to be constant over four time or frequency slots into two time and two frequency slots. The pairwise error probability of the new scheme is evaluated and new code design criteria are obtained to improve the error performance. 64-, 128- and 256-state 4-PSK trellis codes for STF transmission scheme are generated based on these criteria and their frame error performances in an OFDM system are evaluated by computer simulations. Copyright (c) 2007 John Wiley & Sons, Ltd.