This paper presents a new parallel-in-space algorithm for power system transient stability simulations. The nonlinear differential equations are discretized by applying the trapezoidal rule and solved together with the nonlinear algebraic equations for each time step. A network partitioning scheme, which is based on the subdivision of the factorization path tree of the network matrix, is proposed to exploit the parallelism-in-space of the transient stability problem. The parallel version of the very dishonest Newton (VDHN) method, in which the parallel algorithm for solving large sparse network matrix equations is incorporated, is developed and tested on a distributed memory message passing multicomputer. Test results on a sample power system are presented to show the performance of the proposed algorithm.