Telecare medicine information system (TMIS) is developing rapidly and widely used with the support of computer, communication and other advanced technologies. It can ensure the health of residents, improve the shortage of medical resources, and has broad development prospects. To protect the privacy and life safety of patients, and prevent sensitive medical data from being accessed or even tampered by unauthorized parties, identity authentication protocol is widely applied in TMIS. In this paper, we propose an anonymous authentication and key agreement scheme using elliptic curve cryptography (ECC), which uses temporary identities to protect the privacy of patients. We use the well-known formal method under the random oracle (RO) model to prove the security of the scheme, and use the traditional heuristic discussion to prove that our scheme can resist all kinds of known attacks. Additionally, the results of security and performance analysis show that our scheme has less computation complexity and communication overhead, and can be well applied to the telecare medicine information system.