Authentication is the process of determining whether someone or something is, in fact, who or that it is declared to be. It is a client-server based protocol by which a server identifies the identity of a remote client when it logs on to the server through unsecured network. In private and public computer networks, authentication is commonly done through the use of logon passwords. Each user registers initially or is registered by someone else, using an assigned or self-declared password. On each subsequent use, the user must know and use the previously declared password. Internet business and many other transactions require a more stringent authentication process. This paper proposes a new authentication protocol to authenticate remote users using elliptic curves. The proposed protocol has three phases- registration phase, login phase, and authentication phase. When a genuine user wants to login the computer system, he has to key in his identity, password and private keys.