Dynamically selecting an endpoint for a tunnel into an enterprise computing infrastructure. A client dynamically selects a gateway (which may alternatively be referred to as a boundary device or server) as a tunnel endpoint for connecting over a public network (or, more generally, an untrusted network) into an enterprise computing infrastructure. The selection is made, in preferred embodiments, according to least-cost routing metrics pertaining to paths through the enterprise network from the selected gateway to a destination host. The least-cost routing metrics may be computed using factors such as the proximity of selectable tunnel endpoints to the destination host; stability or redundancy of network resources for this gateway; monetary costs of transmitting data over a path between the selectable tunnel endpoints and destination host; congestion on that path; hop count for that path; and/or latency or transmit time for data on that path.