Objectives: This study examined how learning a dance choreography with different teaching pedagogies and different cognitive challenge influenced the development of working memory capacity and motor competence in primary school children. Design: Randomised-controlled trial. Methods: Eighty primary school children (8.8 ± 0.7 years old; 61% females) were recruited and randomly assigned to two experimental groups – a high-cognitive and a low-cognitive group – and a control group. The two experimental groups practiced dance for 7 weeks, twice a week, learning a choreography, while the control group participated in the school standard PE curriculum. In the high-cognitive group, the dance teachers limited visual demonstrations and encouraged children to memorise and recall movement sequences to increase the cognitive challenge. Results: While the pre-to post-test improvements did not statistically differ between experimental groups, the analysis showed that the high-cognitive group statistically improved their working memory capacity (p < 0.01; d = 0.51), while the low-cognitive (p = 0.04; d = 0.48) and control groups did not (p = 0.32; d = 0.17). All three groups improved their motor competence from pre-to post-test, and there was a significant group*time effect (p < 0.01, η_p² = 0.13) with the high-cognitive group showing larger improvement than the control. Conclusions: The results of this study provide initial support that dance practice coupled with a high cognitive challenge could improve working memory capacity and motor competence in children; however, the difference between groups was not statistically significant, and future research is necessary to examine the generalization of this finding.