Abstract: The evolution of cloud computing and Internet of Things (IoT) paradigms has made real time monitoring of patients by remote medical professionals feasible and patients take benefits of healthcare services at home. In these situations patient data gets stored at the centralized healthcare center, from where it can be accessed by a medical professional at regular intervals. However, this makes the patient’s privacy a critical issue due to the open wireless environment. Recently, many authentication schemes for healthcare services have been proposed in the literature and it has been observed that most of the schemes cannot completely achieve the security requirements and they furthermore do not consider the issue of how a medical professional access cloud server data. In this paper, we propose a multi-factor authentication scheme based on elliptic curve cryptography which allows only a legal medical professional to access patient’s medical data stored on the cloud server. Furthermore, the web based AVISPA tool is used for formal analysis and it confirms that the scheme is secure against active and passive attacks including replay and man-in-the-middle attacks. Also, a comparison of security features and performance analysis proves that the scheme offers a strong defense against security attacks and also achieves session key agreement.