In this paper, the study of optimal coordination of directional over-current relays is proposed. The relay coordination problem is non-linear. It typically consists of two groups of control variables (Time Dial Setting: TDS and Plug Setting: PS). The objective function used is the operation time of the main relay in all considered fault cases. The differential evolution (DE) is employed to solve for solutions of optimal relay coordination. It is a stochastic model based on finding the answer from some random method. This algorithm was originally developed from Genetic Algorithm (GA), but the structure is simpler. A 9-bus test system was employed as the test system. The results showed that the DE can find the best solution for optimal relay coordination problems when comparing with those of GA and BFGS.