Multiple sequence alignment is the most fundamentaltask in bioinformatics and computational biology. In thispaper, we present a new algorithm to conduct multiple sequencesalignment based on phylogenetic trees. It is widelyaccepted that a good phylogenetic tree can help producehigh quality alignment, but the direct dynamic programmingsolution grows exponentially. To overcome thisproblem, we first devise a procedure that can produce optimalalignment for three sequences and infer their commonancestor. We then extend the above procedure to computethe alignment of a given tree with more sequences by iterativelyrelabeling the internal nodes. We have implementedour algorithm as a C program package, which can handleboth DNA and protein data and can take simple cost modelas well as complex substitution matrices, such as PAM orBLOSUM series. We test our new method with biologicaland simulated datasets, and compare its performance withthose of other popular multiple sequence alignment tools,including the widely used programs such as ClustalWand T-Coffee.