Visual objects are often defined by multiple features. Therefore, learning novel objects entails learning feature conjunctions. Visual cortex is organized into distinct anatomical compartments, each of which is devoted to processing a single feature. A prime example are neurons purely selective to color and orientation, respectively. However, neurons that jointly encode multiple features (mixed selectivity) also exist across the brain and play critical roles in a multitude of tasks. Here, we sought to uncover the optimal policy that our brain adapts to achieve conjunction learning using these available resources. 59 human subjects practiced orientation-color conjunction learning in four psychophysical experiments designed to nudge the visual system towards using one or the other resource. We find that conjunction learning is possible by linear mixing of pure color and orientation information, but that more and faster learning takes place when both pure and mixed selectivity representations are involved. We also find that learning with mixed selectivity confers advantages in performing an untrained "exclusive or" (XOR) task several months after learning the original conjunction task. This study sheds light on possible mechanisms underlying conjunction learning and highlights the importance of learning by mixed selectivity.