Most existing space-time coding (STC) schemes have been developed for flat fading channels. To obtain antenna diversity gain, they rely on channel state information (CSI) required at the receiver through channel estimation techniques. This paper proposes a new decision feedback decoding scheme for Alamouti-based space-time block coding (STBC) transmission over time-selective fading channels. In wireless channels, time-selective fading effects arise mainly due to Doppler shift and carrier frequency offset, Modelling the time-selective fading channels as the first-order Gauss-Markov processes, we use recursive algorithms such as Kalman filtering, LMS and RLS algorithms for channel tracking. The proposed scheme consists of the symbol decoding stage and channel tracking algorithms. Computer simulations confirm that the proposed scheme shows the better performance and robustness to time-selectivity.