Aspects of the subject matter described herein relate to symmetric routing to a private network. In aspects, a remote client may try to connect to an entity of a private network using a non-routable network address. Upon detecting that connectivity is not established or not possible via a given network address, the client may obtain network data associated with a gateway that provides access to the private network and create a virtual interface where the gateway is the next-hop router. After creating the virtual interface, the client may communicate with entities of the private network using the virtual interface of the client. By sending traffic through the virtual interface with a source address having a prefix associated with the gateway, the client may ensure that traffic sent to and from the private network traverses the gateway.