Network pathways are identified to transfer packets between a pair of regional virtual traffic hubs of a provider network. At a first hub of the pair, a first action is performed, resulting in a transmission of a packet received from a first isolated network to the second hub along a pathway selected using dynamic routing parameters. At the second hub, a second action is performed, resulting in the transmission of the packet to a destination within a second isolated network.