In recent years, distributed generation (DG) has become more common in modern distribution networks (DNs). The presence of these small-scale generation units within a DN brings new challenges to protection engineers, since short-circuit currents tend to increase; additionally, as with microgrids, modern DNs may feature several operational modes depending on their topology and the availability of DG. This paper presents a methodology for the optimal coordination of overcurrent relays (OCRs) in modern DNs with a high presence of DG. Given the fact that protection coordination is a non-linear and non-convex optimization problem, a hybrid harmony search and simulated annealing (HS-SA) approach was implemented for its solution and compared against other techniques, such as conventional HS, genetic algorithm (GA), particle swarm optimization (PSO) and hybrid PSO-HS. Several tests were performed on a DN, considering different operative scenarios as a function of the DG available within the network. A comparison with other works reported in the specialized literature was carried out, evidencing the applicability and effectiveness of the HS-SA technique in solving the optimal OCR coordination problem in modern DNs.