A provider network (100, 200), comprising; two or more regional networks (102, 202) each comprising: one or more virtual private networks each including one or more virtual machines executing on host devices on its respective regional network; a control plane (122, 222) implemented by one or more devices that performs network configuration and management for its respective regional network; and an inter-region coordinator (130, 230), IRC, service comprising one or more IRC servers; wherein the control plane of a first regional network of the two or more regional networks further performs: receive an inter-region peering request from a customer for a first virtual private network on the first regional network via a peering application programming interface, API, of the first regional network, wherein the inter-region peering request specifies a second virtual private network on a second regional network of the two or more regional networks; and generate a create peering record in an inter-region work log on the first regional network for the inter-region peering request; wherein one of the IRC servers on the first regional network performs: obtain the create peering record for the inter-region peering request from the inter-region work log on the first regional network via an API to the inter-region work log; send the create peering record to the control plane of the second regional network according to an API to the control plane of the second regional network; receive a response to the inter-region peering request indicated by the create peering record from the second regional network, wherein the response indicates that the inter-region peering request is pending acceptance; and send the response to the inter-region peering request to the control plane of the first regional network via an API to the control plane of the first regional network. two or more regional networks (102, 202) each comprising: one or more virtual private networks each including one or more virtual machines executing on host devices on its respective regional network; a control plane (122, 222) implemented by one or more devices that performs network configuration and management for its respective regional network; and an inter-region coordinator (130, 230), IRC, service comprising one or more IRC servers; one or more virtual private networks each including one or more virtual machines executing on host devices on its respective regional network; a control plane (122, 222) implemented by one or more devices that performs network configuration and management for its respective regional network; and an inter-region coordinator (130, 230), IRC, service comprising one or more IRC servers; wherein the control plane of a first regional network of the two or more regional networks further performs: receive an inter-region peering request from a customer for a first virtual private network on the first regional network via a peering application programming interface, API, of the first regional network, wherein the inter-region peering request specifies a second virtual private network on a second regional network of the two or more regional networks; and generate a create peering record in an inter-region work log on the first regional network for the inter-region peering request; receive an inter-region peering request from a customer for a first virtual private network on the first regional network via a peering application programming interface, API, of the first regional network, wherein the inter-region peering request specifies a second virtual private network on a second regional network of the two or more regional networks; and generate a create peering record in an inter-region work log on the first regional network for the inter-region peering request; wherein one of the IRC servers on the first regional network performs: obtain the create peering record for the inter-region peering request from the inter-region work log on the first regional network via an API to the inter-region work log; send the create peering record to the control plane of the second regional network according to an API to the control plane of the second regional network; receive a response to the inter-region peering request indicated by the create peering record from the second regional network, wherein the response indicates that the inter-region peering request is pending acceptance; and send the response to the inter-region peering request to the control plane of the first regional network via an API to the control plane of the first regional network. obtain the create peering record for the inter-region peering request from the inter-region work log on the first regional network via an API to the inter-region work log; send the create peering record to the control plane of the second regional network according to an API to the control plane of the second regional network; receive a response to the inter-region peering request indicated by the create peering record from the second regional network, wherein the response indicates that the inter-region peering request is pending acceptance; and send the response to the inter-region peering request to the control plane of the first regional network via an API to the control plane of the first regional network.