In this paper, reliability-based heuristic search methods for maximum likelihood decoding of block codes are considered. Based on the decoding algorithm by Battail and Fang (and its improved technique by Valembois and Fossorier), we deduce a method of reducing the space com-plexity of the heuristic search maximum likelihood decod-ing algorithm. The proposed method is applicable to the heuristic search method with a certain class of evaluation functions. Simulation results show the efficiency of the de-coding algorithm adopting the proposed method.