The estimation of evolutionary history from biomolecular sequences is a major intellectual project in systematic biology and many methods are used to reconstruct phylogenetic (i.e. evolutionary) trees from sequence data. In this paper, we report on an extensive performance analysis of parsimony and two distance-based methods, a popular method called neighbor joining, and a new method developed by Agarwala et al. which approximates the L∞-nearest tree, on more than 260,000 sequence data sets simulated on approximately 500 model trees. Our experiments indicate a decrease in statistical power of the two distance methods as the diameter grows, but also show that parsimony is not as badly affected by the diameter as the distance methods. More generally, the experiments indicate that parsimony is almost always more accurate than the other two methods on reasonable length sequences even under adverse conditions, such as having sites that evolve quickly within the tree, pairs of taxa with large evolutionary distances between them, or large ratios between the highest and the lowest substitution rates on the edges.