Due to the development of information technologies and network technologies, healthcare systems have been employed in many countries. As an important part of healthcare systems, the wireless body area network (WBAN) could bring convenience to both patients and physicians because it could help physicians to monitor patients’ physiological values remotely. It is essential to ensure secure communication in WBANs because patients’ physiological values are very sensitive. Recently, Liu et al. proposed an efficient authentication scheme for WBANs. Unfortunately, Zhao pointed out that their scheme suffered from the stolen verifier-table attack. To improve security and efficiency, Zhao proposed an anonymous authentication scheme for WBANs. However, Zhao’s scheme cannot provide real anonymity because the users’ pseudo identities are constant value and the attack could tract the users. In this paper, we propose a new anonymous authentication scheme for WBANs. Security analysis shows that the proposed scheme could overcome weaknesses in previous scheme. We also use the BAN logic to demonstrate the security of the proposed scheme.