In a changing and competitive business world, business processes are at the heart of modern organizations. In some cases, service level agreements (SLAs) are used to regulate how these business processes are provided. This is usually the case when the business process is outsourced, and some guarantees about how the outsourcing service is provided are required. Although some work has been done concerning the structure of SLAs for business processes, the definition of service level objectives (SLOs) remains a manual task performed by experts based on their previous knowledge and intuition. Therefore, an evidence-based approach that curtails humans involvement is required for the definition of realistic while challenging SLOs. This is the purpose of this paper, where performance-focused process mining, goal programming optimization techniques, and simulation techniques have been availed to implement an evidence-based framework for the definition of SLAs. Furthermore, the applicability of the proposed framework has been evaluated in a case study carried out in a hospital scenario.