Background: When overlapping sets of genes encode multiple traits, those traits may not be able to evolve independently, resulting in constraints on adaptation. We examined the evolution of genetically integrated traits in digital organisms—self-replicating computer programs that mutate, compete, adapt, and evolve in a virtual world. We assessed whether overlap in the encoding of two traits – here, the ability to perform different logic functions – constrained adaptation. We also examined whether strong opposing selection could separate otherwise entangled traits, allowing them to be independently optimized. Results: Correlated responses were often asymmetric. That is, selection to increase one function produced a correlated response in the other function, while selection to increase the second function caused a complete loss of the ability to perform the first function. Nevertheless, most pairs of genetically integrated traits could be successfully disentangled when opposing selection was applied to break them apart. In an interesting exception to this pattern, the logic function AND evolved counter to its optimum in some populations owing to selection on the EQU function. Moreover, the EQU function showed the strongest response to selection only after it was disentangled from AND, such that the ability to perform AND was lost. Subsequent analyses indicated that selection against AND had altered the local adaptive landscape such that populations could cross what would otherwise have been an adaptive valley and thereby reach a higher fitness peak. Conclusions: Correlated responses to selection can sometimes constrain adaptation. However, in our study, even strongly overlapping genes were usually insufficient to impose long-lasting constraints, given the input of new mutations that fueled selective responses. We also showed that detailed information about the adaptive landscape was useful for predicting the outcome of selection on correlated traits. Finally, our results illustrate the richness of evolutionary dynamics in digital systems and highlight their utility for studying processes thought to be important in biological systems, but which are difficult to investigate in those systems.