Accurate reconstruction of phylogenetic trees very of- ten involves solving hard optimization problems, partic- ularly the maximum parsimony (MP) and maximum like- lihood (ML) problems. Various heuristics have been de- vised for solving these two problems; however, they ob- tain good results within reasonable time only on small datasets. This has been a major impediment for large- scale phylogeny reconstruction, particularly for the ef- fort to assemble the Tree of Life—the evolutionary re- lationship of all organisms on earth. Roshan et al. re- cently introduced Rec-I-DCM3, an efficient and accu- rate meta-method for solving the MP problem on large datasets of up to 14,000 taxa. Nonetheless, a drastic improvement in Rec-I-DCM3’s performance is still needed in order to achieve similar (or better) accuracy on datasets at the scale of the Tree of Life. In this paper, we improve the performance of Rec-I-DCM3 via par- allelization. Experimental results demonstrate that our parallel method, PRec-I-DCM3, achieves significant improvements, both in speed and accuracy, over its se- quential counterpart.