Techniques for providing localization at scale for a cloud-based security service are disclosed. In some embodiments, a system/method/computer program product for providing localization at scale for a cloud-based security service includes receiving a connection request at a network gateway of a cloud-based security service; performing a source Network Address Translation (NAT) from a registered set of public IP addresses associated with a tenant; and providing secure access to a Software as a Service (SaaS) using the cloud-based security service.