New teachers are leaving public education at alarming rates leaving states with financial burdens for communities and education losses for students (Owens, 2015; Trans & Smith, 2020). This study examined new teachers' perceptions in Generation Z or within a year of that classification on leadership style and decisions to remain in education. An interpretive qualitative research approach was applied to examine five new teachers' perspectives through narrative inquiry under the lens of the Relational Leadership Theory. This study highlighted the need for school leaders to provide feedback on professional growth, classroom management strategies, and instructional practices. Additionally, this study revealed the need for school administrators to be mindful of timely, personalized, frequent feedback and emotional support for Generation Z teachers.