Teachers are regularly confronted with paradoxes in their profession: clashes between different sets of values, their roles and their personal authenticity, the desire to be open but also detached, and the willingness to encourage students to have their own opinion but at the same time to obey and adapt. In this article, we investigate paradoxes in the music teaching profession with the aim of identifying those that are inherent to the field of music education and do not depend on a specific place or cultural context. To comprehend these paradoxes, we conducted a narrative study focused on the experiences of music teachers as presented through their own stories. This narrative study of 12 music teachers who worked with 10- to 15-year-old students in comprehensive schools was carried out in four European countries. The study applied a three-stage narrative interview strategy that asked teachers to share cases from their experience that implied paradoxes in their professional work. Based on this study, three umbrella categories of paradoxes were identified: paradoxes on curriculum negotiation and co-negotiation with students, free action in a regulated environment, and the double identity of music teachers. The study results offered insights applicable to music teacher education which can be summarized as a proposal to expose prospective music teachers to the paradoxes in their future profession and to discuss strategies that might help them manage these paradoxes.