A method for enabling efficient SSL handshakes through pre-computing of handshake messages, the method includes: receiving, by an appliance, a server certificate identifying a server; generating, by the appliance, at least one of: (i) an SSL server certificate message comprising the received server certificate, (ii) an SSL client certificate request message, and (iii) an SSL hello done message; storing, by the appliance, the generated messages; receiving, by the appliance from a client, an SSL client hello message identifying the server; and transmitting, by the appliance to the client, an SSL server hello message and at least one of the stored messages. Corresponding systems are also described.