We define and discuss the nature of Evidence-based Health Informatics (EBHI), the kind of evidence health informatics researchers must generate to make EBHI a reality, and how we should grade such evidence. We propose adding principle-based evaluation studies to the list of common evaluation study types, and outline how to carry out such studies to generate evidence that will prove useful for establishing EBHI. The main purpose of a principle-based evaluation study is to test the impact on system acceptability, usage or effectiveness of a generalizable system design principle, so we also explore when during the system design process such principles are needed, and which disciplines are most promising as sources of design principles. We conclude with some challenges for EBHI, a list of the benefits of adopting this approach, and a test to ensure that we are advancing in the direction of science, as opposed to pseudoscience.