Among the different heuristics proposed to solve the median string problem, only a few algorithms achieve bounded approximations to the theoretical median string. This family of algorithms is relatively slow. For datasets that exceed hundreds of strings, it takes tens of hours to achieve a result. This behavior limits the applications of these algorithms to real problems where the volume of data is increasing. In this paper, we present a parallelized implementation of a Perturbation-based heuristic to solve the median string problem. A set of experiments is developed that allows us to compare the parallel implementation with its sequential equivalent. Results show that while data increases, the advantage of using parallelism for this problem becomes more evident.