A multi-cloud private communication set-up service enables scalable private connectivity between producers and consumers residing within different public cloud environments. A producer publishes metadata information about a resource within the public cloud environment where the producer resides. The public cloud environment of the publisher is monitored for tagged metadata about new resources. Identified metadata is used to configure a producer-side private link service to a private communication link, and metadata information about the configured producer-side private link service to the private communication link is published within the public cloud environment of the producer. The metadata is identified and used to configure a communication path to the consumer based on a combination of the private communication link, leveraging native multi-VPC network connectivity capabilities between virtual private clouds residing within a public cloud environment, and virtual private network (VPN) tunnel connectivity between the public cloud environments of the producer and the consumer, so that the configured private communication path may be used by the consumer to access the resource from the producer.