The nature and basis of creative thought is the subject of wide-ranging inquiry, yet remains elusive. We focus on a core issue: why do people struggle to solve problems that require a creative insight and what type of support can make success into the norm? Drawing on the idea of relational encoding (e.g., Gentner, Loewenstein, & Thompson, 2003), we sought to improve creative problem solving by activating structured content (relations between objects) in the problem encoding. We developed an alternative to a comparison task: completing a set of sentence frames explaining how pairs of objects in the problem setting relate to one another. In two experiments, we found evidence that participants in the relational encoding group were significantly more likely to solve an insight problem than controls. An important caveat is that the advantage was only found for the easier problems tested - there were no differences for the more difficult problems. We address implications of this work from both theoretical and applied perspectives.