Connectivity Fault Management (CFM) auto-provisioning using Virtual Private LAN Service (VPLS) auto-discovery is described. In one embodiment, an apparatus comprises VPLS logic and configuration logic. The VPLS logic is operable at least to receive and send configuration information for a VPLS instance, where the configuration information comprises: a first value that uniquely identifies the VPLS instance; and a plurality of second values that respectively and uniquely identify a plurality of network elements that are operable to provide the VPLS instance. The configuration logic is operable at least to automatically configure, based on the first value and on the plurality of second values, a CFM association and a local maintenance endpoint (MEP) for the VPLS instance on the apparatus.