We describe the theorization and implementation of a collaborative pilot initiative that took place over the course of one school year as we implemented provocative acts of mentoring for beginning art teachers. The provocations we set in motion were designed to confront prevalent myths of teaching and to embrace the power of artistic exploration to make something generative out of the complex experiences faced by beginning teachers. As our work progressed, we began to see sparks of paradox arise--paradoxes that characterized the (im)possibility of teaching art. By activating mentoring provocations that encouraged all of us to engage with paradoxical tensions, we came to recognize that holding paradox offers an opportunity to embrace the (im)possibility of art education as a space of immanent potential. Excited by the possibilities afforded by holding paradox, we offer three paradoxical tensions that might prompt a re-visioning of mentoring practices with beginning art teachers.