Problem solving is often regarded as one of the most essential cognitive functions in our daily lives, and, for that reason, educational theorists have long stressed the need for its development. As cognitive flexibility is a fundamental characteristic necessary throughout the problem-solving process, the purpose of this study is to analyse students' problem-solving performance after following intra-task flexibility-based training mediated by an intelligent tutoring system. With this aim, 110 fifth and sixth grade students took part in a quasi-experimental study that included six forty-five-minute flexibility-based training sessions preceded and followed by test sessions in order to evaluate eventual problem-solving proficiency improvements. The findings show that intra-task flexibility training enhances students' ability to solve arithmetic word problems, especially when flexibility-related activities are completed sequentially in the same session and not in different sessions. Furthermore, the proposed instruction is particularly helpful in improving girls' problem-solving competence, which can minimize eventual gender gaps and strengthen their STEM vocation.