Methods and apparatus for coordinating inter-region operations in provider networks. An inter-region coordinator (IRC) operates asynchronously to the control planes of regional networks to coordinate inter-region operations. The IRC in a region may include one or more IRC servers. To perform inter-region operations, the servers may implement a local-remote-local method in which a server invokes an API in the local region to get work, sends the work to a control plane of a remote region, receives a response from the remote region, and informs the control plane in the local region of the status of the work.