Evaluation makes a critical contribution to the evidence base for health promotion programs and policy. Because there has been limited research about the characteristics and determinants of evaluation practice in this field, this study audited evaluations completed by health promotion agencies in Victoria, Australia, and explored the factors that enabled or hindered evaluation performance. Twenty-four agencies participated. A systematic assessment of 29 recent evaluation reports was undertaken, and in-depth interviews were carried out with 18 experienced practitioners. There was wide variability in the scope of evaluations and the level of reporting undertaken. Formative evaluation was uncommon, but almost all included process evaluation, especially of strategy reach and delivery. Impact evaluation was attempted in the majority of cases, but the designs and measures used were often not specified. Practitioners strongly endorsed the importance of evaluation, but the reporting requirements and inconsistent administrative procedures of the funding body were cited as significant barriers. Budget constraints, employment of untrained coworkers, and lack of access to measurement tools were other major barriers to evaluation. Capacity building to strengthen evaluation needs to encompass system, organizational, and practitioner- level action. This includes strengthening funding and reporting arrangements, fostering partnerships, and tailoring workforce development opportunities for practitioners.