Techniques for implementing Multi-Protocol Label Switching (MPLS) directly in an SS7 protocol stack enable SS7 network layer protocols to interface, via MPLS, with literally any link layer technology. As a result, label switching can be used seamlessly throughout a collection of heterogeneous networks, including both IP-based and SS7-based networks. An exemplary method of routing SS7 data packets through a heterogeneous packet-switching network using MPLS includes the steps of: establishing an MPLS forwarding equivalence class (FEC), at least one element of the FEC being an SS7 destination; associating a label with the FEC at a first router in the heterogeneous packet switching network; attaching the label, at the first router, to a data packet belonging to the FEC; and forwarding the labeled data packet from the first router to a second router in the communications network. The SS7 destination can be, for example, a Destination Point Code (DPC), a Signaling Connection Control Part (SCCP) global title, or an SCCP subsystem number (SSN).