In this paper, we propose a computationally efficient decoding algorithm for space-time trellis codes in slow Rayleigh fading channels. The proposed scheme is based on a stack algorithm with two key ideas: (i) a variable stack size depending upon the signal-to-noise ratio to avoid the exhaustive search of paths and (ii) a normalized metric, which is defined as each cumulative path metric divided by its own length in the stack, to provide an appropriate comparison of the paths with different lengths. Simulation results demonstrate that the proposed algorithm achieves near-ML performance with significant reduction in complexity, compared with the conventional Viterbi algorithm.