Remote user authentication schemes are used to verify the legitimacy of remote users’ login request. Recently, several dynamic user authentication schemes have been proposed. It can be seen that, these schemes have weaknesses because of using timestamps. The implement of strict and safe time synchronization is very difficult and increases network overhead. In this paper, we propose a new dynamic user authentication based on nonce. Mutual authentication is performed using a challenge-response handshake between user and server, and it avoids the problems of synchronism between smart card and the remote server. Besides, the scheme provides user’s anonymity and session key agreement. Finally, the security analysis and performance evaluation show that the scheme can resist several attacks, and our proposal is feasible in terms of computation cost and communication cost.