More often than not, campus based courses have been criticized as a set of disconnected individual courses and that these courses lack the coherence with the realities of teaching and learning. To this end, one teacher education university has made efforts to make its teacher education program more coherent. Thus, this study reports on this university's preservice teachers' perception of program coherence and associating it with their teaching efficacy. The analysis from 454 preservice teachers, collected through a 30-item perception of program coherence questionnaire and a 12-item Malaysian Teachers' Sense of Efficacy Scale, indicated significant relationships between the two. Overall, the preservice teachers perceived their teacher education programs as fairly coherent. However, more importantly, when these preservice teachers perceived that what they learnt in campus (their theoretical studies) and their practical experiences (during their practicum) were coherent or aligned, this connection helped them to handle issues relating to how they engage students in learning, planning lessons, using appropriate teaching strategies, and classroom management. A coherent teacher education program is able to contribute to preservice teachers' feelings of efficacy and in turn, to a positive stance towards their own functioning as teachers. This finding underscores the importance for foundational theory learnt in the campus to be coherently connected to courses in teaching methodologies and finally to actual classroom teaching. The purpose of any re-design of a teacher education program conceptualized around coherence is about making better connections between theory and practice and to ultimately strengthen teaching.