Despite progress toward gender equity, troubling disparities in mathematical problem-solving performance and related outcomes persist. To investigate why, we build on recurrent findings in previous studies to introduce a new construct, "bold problem solving," which involves approaching mathematics problems in inventive ways. We introduce a self-report survey of bold problem-solving orientation and find that it mediates gender differences in problem-solving performance for both high-achieving middle school students (n = 79) and a more diverse sample of high school students (n = 222). Confidence mediates the relation between gender and bold problem-solving orientation, with mixed results for mental rotation skills and teacher-pleasing tendencies as mediators. Overall, the new bold problem-solving construct appears promising for advancing our understanding of gender differences in mathematics.