Rationale, aims and objectives Although many believe that evidence-based practice (EBP) has great potential, critics have identified limitations including a focus on randomized clinical trial (RCT) evidence to the exclusion of other evidence types and a disregard for the art of medicine. Others have argued, however, that proper application of EBP involves reasoned consideration of a wide variety of information; thus, the dichotomy between medical science and art may be false. We explore the views of executive-level policymakers from the Veterans Health Administration, a leader in the EBP movement, regarding what constitutes evidence and the relative importance of evidence versus practical needs when determining clinical policy. Method We conducted 26 semi-structured qualitative interviews and performed a content analysis. Results Although informants generally believed in the value of EBP and the role of RCTs within it, they also valued other types of evidence. Further, they had concerns that were sometimes antithetical with strict adherence to an evidence-based approach. These included practical concerns, fit with organizational values and with local circumstances, resources, political pressures and patient needs. They were especially concerned about how to address medical conditions that affect many individuals or high-risk populations that have no evidence-based treatment. Conclusion When possible, health care practice should be evidence-based. When this is not possible, health care providers must turn to the art of medicine by using consensus-based best practices. Further, it is important for policymakers and researchers to work in concert to develop EBPs that are practical and meet needs.