Telecare medical information system (TMIS) constructs an efficient and convenient connection between patients and the medical server. The patients can enjoy medical services through public networks, and hence the protection of patients’ privacy is very significant. Very recently, Wu et al. identified Jiang et al.’s authentication scheme had some security drawbacks and proposed an enhanced authentication scheme for TMIS. However, we analyze Wu et al.’s scheme and show that their scheme suffers from server spoofing attack, off-line password guessing attack, impersonation attack. Moreover, Wu et al.’s scheme fails to preserve the claimed patient anonymity and its password change phase is unfriendly and inefficient. Thereby, we present a novel anonymous authentication scheme for telecare medical information systems to eliminate the aforementioned faults. Besides, We demonstrate the completeness of the proposed scheme through the BAN logic. Furthermore, the security of our proposed scheme is proven through Bellare and Rogaways model. Compared with the related existing schemes, our scheme is more secure.