The invention discloses virtual networks using multi-tenant relays. Embodiments are directed to providing a multi-tenant relay service that securely relays data between computer systems. A computer system receives a portion of data that is to be passed from a first computer system belonging to a first tenant to a second different computer system. The instantiated multi-tenant relay service is configured to securely relay data for multiple different tenants. The computer system creates a secure routing channel for routing the data of the first tenant between the first computer system and the second computer system. The secure routing channel applies a unique identifier to each portion of data received from the first tenant. The computer system also routes the received data from the first computer system to the second computer system through the secure routing channel using the applied unique identifier.