The history section of the wikipedia article on handshakes suggests that the Greeks were familiar with the custom at least since the 5th century BC (because we have a sculpture showing Hera and Athena shaking hands that has been dated to the 5th century BC).
Romans also used handshake. It was depicted on Roman coins to symbolize agreement and compromise.