Techniques for dynamic allocation of network address spaces in virtual networks implemented in a service provider system are described. Upon a scaling condition of an allocation rule being determined to be satisfied, a network address space of a virtual network can be automatically expanded or contracted. The scaling condition can be specified by a customer associated with the virtual network. The allocation rule may also include a allocation factor that indicates an amount of network addresses that are to be added to or removed from the virtual network.