Several studies have reported poor executive function (EF) development in deaf children with subsequent impacts on their social and academic attainment. This paper describes the results of a music-based EF intervention designed for deaf children and carried out in two sets of primary schools. This is the first classroom-based EF training study with deaf children, and it also incorporates a replication phase. The intervention was a within-subject crossover design, with 29 deaf children aged 7–11 years who participated in both an EF and an art class control activity, each lasting 10 hours over 5 weeks. Non-verbal EF skills were assessed at pre-test, the crossover point, and post-test. Findings indicated that the EF intervention led to an improvement in participants’ working memory and inhibitory skills in comparison with their performance on the same tasks after the control activity. The findings were not uniform for all EFs targeted nor for all cognitive ability levels in the sample. We discuss the implications of our findings for deaf children with different ability levels and for how EF interventions can be further improved.