Abstract: In order to conquer the computational complexity problem caused by multiple sequence alignment in traditional distance methods, this paper presents a new tree-construction method, which uses a normalized edit distance matrix between pairs of sequences and the Neighbor-Joining algorithm to construct phylogenetic trees Using sequences of Nd5, Nd4, Cytb and mtDNA respectively from 11 vertebrate species and 20 mammalian species, the method can successfully generate consistent phylogenetic trees with those which have been examined by several other approaches.