In this paper, an integrated optimization model based on Gradient-Based Optimizer (GBO) for overcurrent relays coordination along with the challenging practical constraints is proposed. The current proposed effort aims to facilitate the coordination strategy and minimize the technical problems facing the protection/site engineers. The objective function is adapted to minimize the total operating time of the primary relays (TOT) concurrently with satisfying a set of constraints. The algorithm endeavors to fine-tune the relay tripping curve to avoid the false tripping in the case of motor starting and/or transformer inrush conditions. Bear in mind that the selected optimized settings should guarantee that the relay would operate in less time than the thermal withstand capability time of the protected equipment. The proposed model is examined over the distribution portion of the Qarun petroleum isolated network (located inWest desert/Egypt), which presents a practical test case including some scenarios after validating its performance with the IEEE 15-bus network. The proposed complicated optimization problem comprises 128 discrepant inequality constraints for overcurrent relays coordination only having 16 relays with 14 relay pairs. Eventually, GBO demonstrates that it is an efficient algorithm for solving this highly constrained optimization problem by comparing its performance to other robust and well-known algorithms such as particle swarm optimizer (PSO) and water cycle optimizer (WCA). The performance metrics confirm the GBO’s viability over the others. For sake of quantification, (i) for scenario1 of the Qarun test case, the GBO achieves a TOT of 0.7381 s, which indicates 63% and 57% reductions for those obtained by the PSO and WCA, respectively, and (ii) for the 15-bus test case, reductions in the TOT of 14.3% and 16.5% for scenarios 1 and 2, respectively. The proposed tool based on GBO can enhance the protection co-ordination including some practical constraints.