The Hessenberg-Schur method is one of the most efficient and stable algorithms for solving linear matrix equations. When it is applied to the Sylvester equation,AX+X B=C, matrixAis reduced to the Hessenberg form and matrixBto the real Schur for using orthogonal similarity transformations. In this paper we present a parallel algorithm for solving the Sylvester matrix equation whenAandBare in the above-mentioned forms on a Distributed Memory Multiprocessor. Both a complexity analysis and an experimental study of the new algorithm are also presented.