There is a growing awareness that traits do not evolve individually but rather are organized as modular networks of covarying traits. Although the importance of multi-trait correlation has been linked to the ability to evolve in response to new environmental conditions, the evolvability of the network itself has to date rarely been assessed experimentally. By following the evolutionary dynamics of a model bacterium adapting to plant roots, we demonstrate that the whole structure of the trait correlation network is highly dynamic. We experimentally evolved Pseudomonas protegens, a common rhizosphere dweller, on the roots of Arabidopsis thaliana. We collected bacteria at regular intervals and determined a range of traits linked to growth, stress resistance, and biotic interactions. We observed a rapid disintegration of the original trait correlation network. Ancestral populations showed a modular network, with the traits linked to resource use and stress resistance forming two largely independent modules. This network rapidly was restructured during adaptation, with a loss of the stress resistance module and the appearance of new modules out of previously disconnected traits. These results show that evolutionary dynamics can involve a deep restructuring of phenotypic trait organization, pointing to the emergence of novel life history strategies not represented in the ancestral phenotype.