The Internet of Things (IoT) is now a buzzword for Internet connectivity which extends to embedded devices, sensors and other objects connected to the Internet. Rapid development of this technology has led to the usage of various embedded devices in our daily life. However, for resource sharing and communication among these devices, there is a requirement for connecting these embedded devices to a large pool of resources like a cloud. The promising applications of IoT in Government and commercial sectors are possible by integrating cloud servers with these embedded devices. But such an integration of technologies involves security issues like data privacy and authentication of devices whenever information is exchanged between them. Recently, Kalra and Sood proposed an authentication scheme based on elliptic curve cryptography (ECC) for IoT and cloud servers and claimed that their scheme satisfies all security requirements and is immune to various types of attacks. However, in this paper, we show that Kalra and Sood scheme is susceptible to offline password guessing and insider attacks and it does not achieve device anonymity, session key agreement, and mutual authentication. Keeping in view of the shortcomings of Kalra and Sood’s scheme, we have proposed an authentication scheme based on ECC for IoT and cloud servers. In the proposed scheme in this paper, we have formally analyzed the security properties of the designed scheme by the most widely accepted and used Automated Validation of Internet Security Protocols and Applications tool. Security and performance analysis show that when compared with other related schemes, the proposed scheme is more powerful, efficient, and secure with respect to various known attacks.