Systems, methods, and computer-readable media for flushing of Customer Media Access Control (C-MAC) addresses in a PBB-EVPN network are disclosed. A first provider edge (PE) device can maintain a plurality of service instances configured on a first interface. The first PE device can detect at least one failed ethernet virtual circuit (EVC) on the first interface and identify at least one service instance from the plurality of service instances that is associated with the at least one failed EVC. The PE device can send, to a second PE device, a C-MAC flush notification message that identifies the at least one service instance and the message can cause the second PE device to remove C-MAC addresses corresponding to the at least one service instance and the B-MAC address for the first interface.