Although the notion of proof is important for all learners’ mathematical experiences, there has been limited attention to what it might involve and look like to introduce students and prospective teachers to proof. In this paper we argue for the importance of having a coherent approach to introducing students and prospective teachers to proof, and we discuss the theoretical basis of a learning trajectory relevant to both groups. We also discuss an instructional sequence that aimed to promote the learning trajectory among English secondary students and U.S. prospective elementary teachers, drawing on data from two multi-year design experiments. The learning trajectory comprises two milestones: (1) seeing a need to learn about proof and (2) developing an operationally functional conceptualization of proof. The “need” in milestone 1 entails an aspect of epistemological justification applicable to both students and prospective teachers, and a further aspect of pedagogical justification applicable to prospective teachers.