Undergraduate computer science (CS) students often struggle in theoretical, proof-based courses, which require formal proof and rigorous reasoning skills. Despite ongoing efforts to improve these courses, challenges remain due to the complex nature of the material and CS students’ perception that it has limited practical relevance. In this work, we take a human-centered approach to investigate the challenges and needs of both instructors and students in such courses. Through semi-structured interviews with 16 instructors and 20 students followed by a thematic analysis of the resulting data, we develop the CNPE framework, which captures the Challenges and Needs in Proof Education. While rooted in our local experience, the CNPE framework can be adapted for broader application, underscoring the value of understanding stakeholder challenges and needs before designing educational interventions.