Evaluating Software testability can assist software managers in optimizing testing budgets and identifying opportunities for refactoring. In this paper, we abandon the traditional approach of pursuing testability measurements based on the correlation between software metrics and test characteristics observed on past projects, e.g., the size, the organization or the code coverage of the test cases. We propose a radically new approach that exploits automatic test generation and mutation analysis to quantify the amount of evidence about the relative hardness of identifying effective test cases. We introduce two novel evidence-based testability metrics, describe a prototype to compute them, and discuss initial findings on whether our measurements can reflect actual testability issues.