The purpose of this article is to investigate the perception of teachers on tolerance and the way in which tolerance can be taught in education institutions. It is based on interviews with 152 teachers from 28 high schools in four cities (Batu, Jember, Lamongan, and Nganjuk) in East Java, Indonesia, as well as Focus Group Discussion (FGD) with high school principals, teachers, and representatives from the Office of Education in the city of Surabaya. While our findings confirm the previous studies about the role of teachers in shaping students' approach to diversity, we put forth an argument that the concept of tolerance has not been whole-heartedly embraced by Indonesian teachers. The absence of interreligious learning renders questionable the effectiveness of cultivating tolerance in a multi-religious Indonesia. The first part of the article offers a theoretical discussion on the link between education and tolerance. In the second part, our findings will be presented, including teachers' view of tolerance, the way tolerance is taught, and various strategies develop to prevent intolerance. The final part discusses the findings within a broader context of religious literacy and citizenship education.