Movement creativity is a key factor in motor development in children, yet very few exercise programs promote the development of motor creativity in children. To address this gap in the literature, this study tested the effectiveness of a creative exercise program on children's motor and cognitive creativity, and their probability of adaptation to exercise challenges. A total of 140 fourth-grade students from 8 elementary schools (M[subscript age] = 9.56 ± 0.61 years) were randomly allocated to a conventional or creative program for 10 sessions over a period of 3 months. A nonlinear pedagogical framework was used to educate coaches and to transform the conventional program into a creative one. Following the 3-months intervention, children in the creative program displayed higher originality in thinking and improved fluency and flexibility in movement than children in the conventional program. No differences were observed on the probability of adaptation to exercise challenges between both programs. The findings revealed that introducing elements of the nonlinear pedagogy into a conventional exercise program can increase children's cognitive and motor creativity. This study provides educators with evidenced-based guidelines for maintaining, or even fostering, both cognitive and motor creativity in children. Manipulation of constrains, variability, improvisation, and problem solving appear to be key principles for developing creativity among children.