Variation is the basis for evolution, and understanding how variation can evolve is a central question in biology. In complex phenotypes, covariation plays an even more important role, as genetic associations between traits can bias and alter evolutionary change. Covariation can be shaped by complex interactions between loci, and this genetic architecture can also change during evolution. In this article, we analyzed mouse lines experimentally selected for changes in size to address the question of how multivariate covariation changes under directional selection, as well as to identify the consequences of these changes to evolution. Selected lines showed a clear restructuring of covariation in their cranium and, instead of depleting their size variation, these lines increased their magnitude of integration and the proportion of variation associated with the direction of selection. This result is compatible with recent theoretical works on the evolution of covariation that take the complexities of genetic architecture into account. This result also contradicts the traditional view of the effects of selection on available covariation and suggests a much more complex view of how populations respond to selection.