Nowadays, microgrids play a significant role in the development of modern distribution networks (DNs). In this context, the ever increasing presence of renewable distributed generation (DG) in microgrids has imposed new challenges in protection coordination, rendering traditional coordination schemes inefficient. Thus, it is essential to explore new approaches for protection coordination that take into account specific features of microgrids, such as the presence of DG and the fact that they may operate under different operational modes or topologies. This paper proposes a novel approach for the optimal coordination of over-current relays (OCRs) in microgrids that considers three optimization parameters for each relay: time multiplying setting, plug setting current and characteristic curve. To show the applicability of the proposed approach, several tests were carried out using an IEC benchmark microgrid and a modified version of the IEEE 30 bus test system. Three metaheuristic techniques were implemented for solving the optimal coordination problem, namely: a genetic algorithm (GA), particle swarm optimization (PSO) and a teaching–learning based optimization (TLBO) algorithm. A comparison of results with other coordination models reported in the specialized literature evidenced the applicability and effectiveness of the proposed approach.