Previous research has suggested that personal need for structure (PNS) is negatively related to creative performance. In this article, it is argued that this relation, in fact, depends on another personality variable: personal fear of invalidity (PFI). When PFI is high, PNS should indeed be negatively associated with creativity. However, PNS should be positively associated with creativity when PFI is low, because this combination enables people to take a structured approach to creative tasks and this can be helpful to overcome their reliance on conventional and accessible task strategies. In four studies, this hypothesis is tested using different measures of creative performance. The expected interaction effect is found for measures of ideational fluency and measures of originality but not for measures of flexibility. Moreover, it is shown that the interaction effect between PNS and PFI is mediated by perseverance within thought categories.