The success of a power system protection scheme so much depends upon the optimal coordination of its different units, which are protective relays. The task of finding the optimal set of relay parameters or settings can be achieved by solving a nonlinear and highly constrained optimization problem. This paper develops a new variable neighborhood search (VNS) algorithm as a potent tool for coordinating the controlling parameters of directional overcurrent relays (DOCRs), particularly the current settings and tripping times. VNS is an optimization algorithm which works based on a systematic change of neighborhood while searching the optimal solution of a given problem in both descent and perturbation phases. The performance of the proposed VNS-based algorithm is demonstrated on the 8-bus, 9-bus and 15-bus power system networks with diverse scenarios. The obtained outcomes are compared with other competitive customary algorithms. Thus, the superiority of the proposed technique is validated in coordinating the DOCRs for better protection of the power system.