A computer-implemented method, comprising the steps of: providing, by one or more computing systems of a network service, an interface for use in configuring virtual networks provided by the network service for multiple users of the network service; receiving, by the one or more computing systems and via the provided interface, configuration information for a virtual network from a user of the multiple users, the received configuration information specifying virtual machines (207a, 207d) to be hosted by the network service as part of the virtual network, and a range of virtual network addresses to use for the virtual machines in the virtual network, wherein the range of virtual network addresses overlaps with a virtual network address range used by a remote computer network of the user and wherein the received configuration information further specifies information for a virtual private network, VPN, connection from the virtual network to the remote computer network of the user; receiving, by the one or more computing systems and via the provided interface, virtual machine configuration information for the virtual machines to be hosted by the network service as part of the virtual network; provisioning, automatically by the one or more computing systems, the virtual machines into the virtual network according to the virtual machine configuration information, wherein the virtual machines are provisioned on selected servers of the network service and assigned virtual network addresses from the range of virtual network addresses, and wherein the virtual network enables communications between the virtual machines via their respective virtual network addresses in accordance with the configuration information of the virtual network, wherein the provisioning is initiated based on receiving the virtual machine configuration information; and establishing, automatically, the VPN connection for use by the virtual network. providing, by one or more computing systems of a network service, an interface for use in configuring virtual networks provided by the network service for multiple users of the network service; receiving, by the one or more computing systems and via the provided interface, configuration information for a virtual network from a user of the multiple users, the received configuration information specifying virtual machines (207a, 207d) to be hosted by the network service as part of the virtual network, and a range of virtual network addresses to use for the virtual machines in the virtual network, wherein the range of virtual network addresses overlaps with a virtual network address range used by a remote computer network of the user and wherein the received configuration information further specifies information for a virtual private network, VPN, connection from the virtual network to the remote computer network of the user; receiving, by the one or more computing systems and via the provided interface, virtual machine configuration information for the virtual machines to be hosted by the network service as part of the virtual network; provisioning, automatically by the one or more computing systems, the virtual machines into the virtual network according to the virtual machine configuration information, wherein the virtual machines are provisioned on selected servers of the network service and assigned virtual network addresses from the range of virtual network addresses, and wherein the virtual network enables communications between the virtual machines via their respective virtual network addresses in accordance with the configuration information of the virtual network, wherein the provisioning is initiated based on receiving the virtual machine configuration information; and establishing, automatically, the VPN connection for use by the virtual network.