Disclosed are various embodiments for managing network address allocations using prefix allocation trees. In one embodiment, a request is received to allocate a particular network address block. The request specifies one or more attributes and at least one of a prefix or a size for the particular network address block. A prefix allocation tree is updated to indicate that the particular network address block corresponding to the prefix is allocated instead of free and to associate the attribute(s) with the particular network address block. An identification of an allocation of the network address block is returned in response to the request to allocate the particular network address block. An attribute index of the prefix allocation tree is updated asynchronously to index the attribute(s) in association with the particular network address block.