This paper examines the attitudes and practices of Australian health promotion practitioners toward evidence-based practice (EBP). The study used a survey methodology and questionnaires were sent to 1114 members of the Australian Health Promotion Association. A response rate of 27% (n = 277) was achieved. The data showed that the vast majority of participant's attitudes toward EBP was very welcoming. However, in practice the impact of EBP was limited. Participants identified a range of significant barriers to implementing EBP including organizational culture, policy directives and lack of resources. A range of concerns was also identified regarding the applicability of the medically based EBP model within health promotion, which is based upon a social model of health. The findings highlight the importance of acknowledging the complexity of health promotion interventions and working toward developing an appropriate evidence base.