In this paper we present a protocol for Certified E-Mail that ensures temporal authentication. We first slightly modify a previously known three-message optimistic protocol in order to obtain a building block that meets some properties. We then extend this basic protocol enhancing it with the temporal authentication by adding a single message, improving the message complexity of known protocols. The fairness of the protocol is ensured by an off-line Trusted third party that joins the protocol only in case one of the players misbehaves. In order to guarantee temporal authentication we assume the existance of an on-line time stamping server.