Program evaluation is essential to inform decision making, contribute to the evidence base for strategies, and facilitate learning in health promotion and disease prevention organizations. Theoretical frameworks of organizational learning, and studies of evaluation capacity building describe the organization as central to evaluation capacity. Australian prevention organizations recognize limitations to current evaluation effectiveness and are seeking guidance to build evaluation capacity. This qualitative study identifies organizational facilitators and barriers to evaluation practice, and explores their interactions in Australian prevention organizations. We conducted semi-structured interviews with 40 experienced practitioners from government and non-government organizations. Using thematic analysis, we identified seven key themes that influence evaluation practice: leadership, organizational culture, organizational systems and structures, partnerships, resources, workforce development and training and recruitment and skills mix. We found organizational determinants of evaluation to have multi-level interactions. Leadership and organizational culture influenced organizational systems, resource allocation and support of staff. Partnerships were important to overcome resource deficits, and systems were critical to embed evaluation within the organization. Organizational factors also influenced the opportunities for staff to develop skills and confidence. We argue that investment to improve these factors would allow organizations to address evaluation capacity at multiple levels, and ultimately facilitate effective evaluation practice.