Humans and other animals must sometimes “think outside the box” to discover better strategies that solve old problems under novel conditions, but how the metaphorical “box” itself constrains learning is unknown. In operant tasks, the mechanisms behind learning are often framed just in terms of reinforcing success or punishing failure, and any predisposed strategies for guiding actions are ignored. In ethological behaviors though, animals often have instinctive predispositions in how they approach an evolutionarily adapted task but can also learn new ways to do better. Combining chemogenetics, modeling and electrophysiology in mice, we investigate learning in a natural parenting task – pup search and retrieval – and reveal that animals’ predisposed strategy for searching can impede learning a more efficient strategy. Specifically, female mice are innately motivated to find pups and rely on a win-stay strategy for searching, but can learn to switch to using a novel artificial sound that reliably signals where a pup will be found. We discovered, unexpectedly, that chemogenetic silencing of medial prefrontal cortex accelerates learning to use the sound strategy. A phenomenological model of neural competition between the two strategies accurately predicts animals’ learning curves and the effect of chemogenetic silencing on learning. In vivo electrophysiology in freely running mice during learning uncovered an auditory cortical neural correlate of the auditory strategy that increases, and a prefrontal cortical neural correlate of the win-stay strategy that decays, over the course of learning, thereby substantiating putative substrates of the competition model. Our findings expose a surprising competitive relationship between the prefrontal and sensory cortex during the transition from a predisposed default to a novel, out-of-the-box strategy. Our work thus expands the concept of cognitive flexibility and learning to include how new modalities for informative cues are discovered and come to prevail in decisions.