We analyze the performance of likelihood-based approaches used to reconstruct phylogenetic trees. Unlike other techniques such as Neighbor-Joining (NJ) and Maximum Parsimony (MP), relatively little is known regarding the behavior of algorithms founded on the principle of likelihood. We study the accuracy, speed, and likelihood scores of our representative likelihood-based methods (fastDNAml, MrBayes, PAUP*-ML, and TREE-PUZZLE) that use either Maximum Likelihood (ML) or Bayesian inference to find the optimal tree. NJ is also studied to provide a baseline comparison. Our simulation study is based on random birth-death trees, which are deviated from ultrametricity, and uses the Kimura 2-parameter +Gamma model of sequence evolution. We find that MrBayes (a Bayesian inference approach) consistently outperforms the other methods in terms of accuracy and running time.