This paper presents an application of parallel Genetic Algorithm-Tabu Search (GA-TS) algorithm to search an optimal solution of a service restoration in distribution systems. The main objective of service restoration of distribution systems is, when a fault or overload occurs, to restore as much load as possible by transferring the do-energized load in the out of service area via network reconfiguration to the appropriate adjacent feeders at minimum operational cost without violating operating constraints, which is a combinatorial optimization problem. This problem has many constraints with many local minima to solve the optimal switch position. This paper develops parallel GA-TS algorithm for service restoration of distribution systems. In parallel GA-TS, GA operators are executed for each processor. To prevent solutions of low fitness from appearing in the next generation, strings below the average fitness are saved in the tabu list. If best fitness of the GA is not changed for several generations, TS operators are executed for the upper $10\%$ of the population to enhance the local searching capabilities. With migration operation, best string of each node is transferred to the neighboring node after predetermined iterations are executed. For parallel computing, we developed a PC cluster system consists of 8 PCs. Each PC employs the 2 GHz Pentium IV CPU and is connected with others through ethernet switch based fast ethernet. To show the validity of the proposed method, proposed algorithm has been tested with a practical distribution system in Korea. From the simulation results, we can find that the proposed algorithm is efficient for the distribution system service restoration in terms of the solution quality, speedup, efficiency and computation time.