Mathematics teachers are expected to engage their students in critiquing and constructing viable arguments. These classroom expectations are necessary, given that proof is a central mathematical activity. However, mathematics teachers have been provided limited opportunities as learners to construct arguments and critique the reasoning of others, and hence have developed perceptions of proof as an object that must follow a strict format. In this article, we describe a four-part instructional sequence designed to broaden and deepen teachers' perception of the nature of proof. We analyzed participants' reflections on the instructional sequence in order to gain insight into (a) the differences between this instructional sequence and participants' previous proof learning opportunities and (b) the ways this activity was influential in transforming participants' perceptions of proof. Participants' previous learning experiences were focused on memorizing and reproducing textbook or instructor proofs, and our sequence was different because it actively and collaboratively engaged participants in constructing their own arguments, critiquing others' reasoning, and creating criteria for what counts as proof. Participants found these activities transformative as they became more clear about what counts as proof, began to view proof as socially negotiated, and expanded their conception of proof beyond a rigid structure or format.