Techniques for providing connectivity fault management (CFM) for a multi-tiered network are described herein. In one embodiment, a link trace message (LTM) is received at a provider edge (PE) router and originated from a first Ethernet node and destined to a second Ethernet node, where the PE router interfaces an Ethernet and a multi-protocol label switching (MPLS) network. In response, the PE router initiates an MPLS trace session, including generating an MPLS trace message based on the LTM message to one or more MPLS nodes along a path between the first and second Ethernet nodes within the MPLS network. Subsequently, in response to one or more MPLS trace reply messages from the MPLS nodes of the MPLS network, the PE router generates a first link trace reply (LTR) message and sends the first LTR message to the first Ethernet node over the Ethernet. Other methods and apparatuses are also described.