In this paper, we propose and analyze a new parallel SOR method, the PSOR method, formulated by using domain partitioning and interprocessor data communication techniques. We prove that the PSOR method has the same asymptotic rate of convergence as the Red/Black (R/B) SOR method for the 5-point stencil on both strip and block partitions, and as the four-color (R/B/G/O) SOR method for the 9-point stencil on strip partitions. We also demonstrate the parallel performance of the PSOR method on four different MIMD multiprocessors (a KSR1, the Intel Delta, a Paragon and an IBM SP2). Finally, we compare the parallel performance of PSOR, R/B SOR and R/B/G/O SOR. Numerical results on the Paragon indicate that PSOR is more efficient than R/B SOR and R/B/G/O SOR in both computation and interprocessor data communication.