Due to rapid interest on the applications of convolutional tail-biting to communication systems, several suboptimal algorithms have been proposed to achieve near-optimal Word error rate (WER) performances with circular Viterbi decoding approach. Among them, the wrap-around Viterbi algorithm (WAVA) proposed in  is the one with least decoding complexity. Very recently, a maximum likelihood (ML) decoding algorithm has been proposed in . The scheme has two phases. The Viterbi algorithm is applied to the trellis of the convolutional tail-biting code and the information obtained in the first phase is used by algorithm A*, which is performed to all subtrellises, in the second phase. In this work, a new two-phase ML decoding algorithm is proposed. From the simulation results for the (2, 1, 12) convolutional tail-biting code, the proposed algorithm has 16 times less average decoding complexity in the second phase when compared to the one using algorithm A*and 15123 times less than that of the WAVA, respectively, when SNRb = 4 dB.