Parallel computing is an effective approach to transient stability real-time simulation of large-scale power system. A new parallel algorithm for power system transient stability simulation is proposed by combining Gauss integration method and the extended Sherman-Morrison formula. The algorithm adopts the s-stage 2s-order Gauss method to convert the differential-algebraic equations into a set of nonlinear algebraic equations by multi-stages discretization, while the algebraic system is solved using rigorous Newton method. On this basis, the whole Jacobian matrix involved in Newton method is splitted to a block diagonal matrix and a block constant coefficients matrix according to s time points, and then based on the block diagonal matrix, the computing tasks at s time points are fully decoupled through the extended Sherman-Morrison matrix inverse formula. The proposed algorithm preserves the good convergence of rigorous Newton method and meanwhile has a high degree of parallelism both in time and in space. For test, the proposed algorithm has been implemented on a multi-core computer by use of OpenMP technology, and the results for two example systems show that the proposed parallel algorithm can obtain effective speedup and parallel efficiency. This work is supported by National Natural Science Foundation of China (No. 51377098 and No. 50977052).