Methods and apparatus for pre-configured virtual gateways for isolated virtual networks are described. An isolated virtual network (IVN) is configured at a provider network on behalf of a customer. The IVN includes one or more devices whose network addresses are not accessible from the public Internet. In response to a request from a connectivity intermediary, a virtual private gateway (VPG) is established, configurable to enable connectivity between IVNs of the provider network and devices outside the provider network. The VPG is included within a set of candidate VPGs indicated programmatically to the customer. Connectivity is established between the customer's IVN and an external device via the VPG.