In general, in an aspect, a method for providing an outbound gateway protection includes provisioning one or more worker gateways located in a first gateway virtual private cloud, the one or more worker gateways sharing configuration data with the controller gateway, provisioning one or more load balancer gateways in one or more client virtual clouds, the one or more client virtual clouds each comprising one or more clients, the one or more load balancer gateways distributing client requests among the worker gateways, assigning groups of the one or more clients to one of the one or more load balancer gateways based on requests from a majority of the worker gateways, and communicating outbound network traffic from the clients via the assigned load balancer gateways.