Anonymous user authentication is an important but challenging task for wireless communications. In a recent paper, Das proposed a smart card-based anonymous user authentication protocol for wireless communications. The scheme can protect user privacy and is believed to be secure against a range of network attacks even if the secret information stored in the smart card is compromised. In this paper, we reanalyze the security of Das’ scheme, and show that the scheme is in fact insecure against impersonation attacks. We then propose a new smart card-based anonymous user authentication protocol for wireless communications. Compared with the existing schemes, our protocol uses a different user authentication mechanism, which does not require different entities to maintain a synchronized clock.We show that the proposed new protocol can provide stronger security and better efficiency and scalability than previous schemes.