Abstract: There are different goals in a non-repudiation protocol to be considered for different application. However, there are some goals to be considered in a non-repudiation protocol for E-mail: non-repudiation of both parties; fairness to both message sender and message receiver with respective to their control over the completion of a transaction; the degree of trust on a third party; keeping E-mail confidentiality; and decreasing the number of interaction. In this paper, a new non-repudiation protocol for E-mail is proposed for resolving the existent problems: unfairness, confidentiality not well protected, and many numbers of interaction by using formal analysis, and the new protocol is proven to be able to provide non-repudiation of sender and receiver, fairness and validity of evidence.