Many different methods to mitigate spam in the internet have been proposed. However, the most promising ones require fundamental changes to mail protocol itself. Other methods are based on filtering, but still require the end-user to verify the results. We propose a different approach, that requires email senders to traverse a kind of handshake before sending an initial email to a new contact.Our method, called Mail-Shake, is based on two facts. First,spammers need valid email addresses to deliver their spam to.Second, spammers do not require real inboxes for their sender addresses, as replies are not expected. This allows complete automation of the spamming process, sending email at almost no cost. If we can decrease the number of valid email addresses a spammer can collect and increase the cost of sending email,spamming becomes uninteresting as the effort is too high in contrast to the win.