Virtual networks may be launched in a provider network with an initial IP address space (e.g., an IPv4 CIDR block). Methods are described that allow additional IP address spaces to be added to a virtual network. A new IP address space for a virtual network may be specified via an API. The specified space may be checked to insure that it does not overlap with IP spaces that are associated with the virtual network. If there are no overlaps, the space is added to the network, for example by adding the space to the network's route tables.