Methods and apparatuses for fast convergence in Layer 2 overlay network are described. Forwarding of Layer 2 (L2) traffic addressed to one or more remote L2 destinations is performed according to a remote L2 (RL2) instance, where the RL2 instance identifies a primary path for forwarding the traffic towards the remote L2 destinations, and a provider edge service label (PESL) instance associated with a broadcast domain including one or more network devices for forwarding the L2 traffic towards the L2 destination, and where the PESL instance is identified with a unique immutable PESL instance label. In response to a network event, an update of the RL2 instance is performed. The update results in an update of a data plane for forwarding the L2 traffic without necessitating an update of forwarding table entries for each one of the one or more remote L2 destination.