Optimal coordination of overcurrent relays has become a major challenge in power distribution systems due to the increasing participation of distributed generation (DG) and electric vehicle (EV) charging stations, especially vehicle-to-grid (V2G) technology. This paper proposes a novel approach for optimal coordination of directional overcurrent relays (DOCRs) to achieve the minimum operating time and obtain optimal tuning in terms of time dial setting (TDS) and pick-up current (IP) considering V2G integration. The optimization was conducted using three different Artificial Intelligence (AI) techniques: grey wolf optimization (GWO), cuckoo search (CS), and Hunger Games Search (HGS), and was performed on two systems: IEEE 33-bus system and a local grid located in El-Shorouk City–district#8 (ShC-D8), Cairo, Egypt. The proposed methodology is constructed and validated on ETAP and MATLAB software packages. The simulation results demonstrate that the proposed optimization techniques provide high dynamic performance and accurate coordination of DOCRs. The results show that HGS achieves the minimum operating time of all overcurrent relays as compared with GWO and CS. The effect of V2G integration on the coordination methodology is also considered. The proposed approach provides a significant contribution to the field of power system protection and can help improve the reliability and efficiency of power distribution systems with V2G integration.