Nearly one in three students in the United States today is negatively impacted by bullying. Teachers can play a critical role in stopping bullying-related violence, but many struggle with how to engage students in difficult conversations. Traditional classroom-based pedagogy used to teach communication skills (e.g., modeling & role-play) is inefficient and limited in scope. Recent advances in Artificial Intelligence have resulted in the development of virtual pedagogical agents designed to simulate authentic conversations and can be leveraged to teach vital communication skills. This exploratory study examines the effectiveness of a "virtual role-play" (VRP) tool developed to help teacher candidates effectively respond to classroom bullying by providing them with opportunities to engage in repeated, authentic practice conversations. We hypothesized that practice in simulated conversations provided by VRP would improve teacher candidates' communication skills by improving their fluency in responding to classroom bullying. Our findings revealed that the repeated practice afforded by VRP improved candidates' fluency by helping them focus on more refined word choice, reducing their reliance on written notes, and improving their nonverbal skills. Implications regarding use of VRP to prepare candidates to communicate in bullying situations are discussed. [This article was published in "Journal of Technology and Teacher Education" (EJ1130990).]