To the best of our knowledge, no comprehensive scientific study has investigated these challenges and barriers in all Healthcare Facilities (HCFs) across the Kingdom of Saudi Arabia (KSA). This research, which is undertaken based on the Saudi Telemedicine Network roadmap and in collaboration with the Saudi Ministry of Health (MOH), is aimed at identifying the principle predictive challenges and barriers in the context of the KSA, and understanding the perspective of the decision makers of each HCF type, sector, and location. Three theories are used to underpin this research: the Unified Theory of Acceptance and Use of Technology (UTAUT), the Technology–Organisation–Environment (TOE) theoretical framework, and the Evaluating Telemedicine Systems Success Model (ETSSM). This study applies a three-sequential-phase approach by using three mixed methods (i.e., literature review, interviews, and questionnaires) in order to utilise the source triangulation and the data comparison analysis technique. The findings of this study show that the top three influential barriers to adopt and implement telemedicine by the HCF decision makers are: (i) the availability of adequate sustainable financial support to implement, operate, and maintain the telemedicine system, (ii) ensuring conformity of telemedicine services with core mission, vision, needs and constraints of the HCF, and (iii) the reimbursement for telemedicine services.