Modern information technology has been utilized progressively to store and distribute a large amount of healthcare data to reduce costs and improve medical facilities. In this context, the emergence of e-Health clouds offers novel opportunities, like easy and remote accessibility of medical data. However, this achievement produces plenty of new risks and challenges like how to provide integrity, security, and confidentiality to the highly susceptible e-Health data. Among these challenges, authentication is a major issue that ensures that the susceptible medical data in clouds is not available to illegal participants. The smart card, password and biometrics are three factors of authentication which fulfill the requirement of giving high security. Numerous three-factor ECC-based authentication protocols on e-Health clouds have been presented so far. However, most of the protocols have serious security flaws and produce high computation and communication overheads. Therefore, we introduce a novel protocol for the e-Health cloud, which thwarts some major attacks, such as user anonymity, offline password guessing, impersonation, and stolen smart card attacks. Moreover, we evaluate our protocol through formal security analysis using the Random Oracle Model (ROM). The analysis shows that our proposed protocol is more efficient than many existing protocols in terms of computation and communication costs. Thus, our proposed protocol is proved to be more efficient, robust and secure. © 2020 Chongqing University of Posts and Telecommunications