The minimum common string partition problem is an NP-hard combinatorial optimization problem with applications in computational biology. In this work we propose an iterative probabilistic tree search algorithm for tackling this problem. By means of an extensive experimental evaluation we show the superiority of our approach in comparison to a standard greedy algorithm and a metaheuristic based on ant colony optimization from the related literature. © Springer International Publishing Switzerland 2014.