In accordance with a designation of a private alias endpoint as a routing target for traffic directed to a service from within an isolated virtual network of a provider network, a tunneling intermediary receives a baseline packet generated at a compute instance. The baseline packet indicates a public IP (Internet Protocol) address of the service as the destination, and a private IP address of the compute instance as the source. In accordance with a tunneling protocol, the tunneling intermediary generates an encapsulation packet comprising at least a portion of the baseline packet and a header indicating the isolated virtual network. The encapsulation packet is transmitted to a node of the service.