Techniques for dynamically scaling instances of virtual private network (VPN) gateway in a cloud computing system are disclosed herein. In one embodiment, a method includes determining whether a number of packets processed by a first instance of the VPN gateway exceeds a preset threshold. In response to determining that the number of packets exceeds the preset threshold, a new security association (SA) corresponding to a portion of the VPN network traffic is created. Upon completion of creating the SA, a load balancing policy at a load balancer is modified to forward a portion of the network traffic to a second instance of the VPN gateway when an incoming packet contains a security parameter index (SPI) corresponding to the created SA in its EPS header.