Aspects of the disclosure provide for a proxyless NAT infrastructure with dynamic port allocation. A proxyless NAT infrastructure is configured to perform NAT between a network of virtual machines (VMs) and a device external to the network, without a device, such as a NAT server or a router, acting as a proxy. A system can include a control plane for provisioning VMs of a network, including configuring each VM to perform NAT and initially assigning a number of ports for communicating with other devices. The control plane maintains a feedback loop-receiving data characterizing port usage and network traffic at ports allocated to the various VMs and scaling the port allocation for each VM based on the received data. The control plane can allocate additional ports as determined to be needed by a VM, and later retrieve the ports to be reused for other VMs.