The Maximum Parsimony (MP) problem aims at reconstructing a phylogenetic tree from DNA sequences while minimizing the total number of genetic transformations. In this paper two different metaheuristic algorithm for finding near-optimal solutions for the MP problem are proposed: iterated local search (ILS) and simulated annealing (SA). Different possibilities for the key components of these algorithms were carefully analyzed in order to find the combination of them offering the best quality solutions to the problem at a reasonable computational effort. The performance of both metaheuristics is investigated through extensive experimentation over well known benchmark instances showing that our SA algorithm is able to improve some previous best-known solutions.