Example methods and apparatus to form secure cross-VPN (virtual private network) communication sessions in multiprotocol label switching (MPLS)-based networks are disclosed. An example method comprises receiving a communication session initiation request from a first device associated with a first MPLS-based VPN, determining whether the communication session initiation request is directed to a second device associated with a second MPLS-based VPN, sending a cross-VPN link setup request to a route reflector to enable a cross-VPN communication path over which the first and second devices are permitted to communicate when the communication session initiation request is directed to the second device associated with the second VPN, and facilitating a communication session between the first and second devices via the communication path enabled by the route reflector.