Problem-based learning (PBL) has been gaining in popularity, especially within the context of STEM-based (science, technology, engineering, and mathematics) schools. Program assessments for these schools typically focus on student standardized test scores rather than the needs of the teachers. This study utilized anecdote circles, storytelling via moderated group discussions, to investigate teachers' needs related to developing and implementing authentic, interdisciplinary PBL activities in an urban, public STEM high school. Teacher experiences and viewpoints were explored within three broad themes: assessment; coaching and training; and authentic learning. The analyses provide insights for transitioning a school for effective PBL implementation as well as improving teaching and learning best practices. Recommendations to improve PBL practice based on the study's results are also included.