A signed employment offer paper in your hands does. This also allows you to get your worker's permit (which you'll need before your starting date, at least in Germany). You may not even be able to get in the country without the paper.
E-mails and phone calls do not account as offers / contracts. Scans are borderline valid, so preferably they should physically mail you the offer for you to sign after you get an e-mail/phone call.
One thing I've done is receive two copies of the offer, one personal and one for the company, and since I was suppose to arrive asap I took both with me and delivered their copy personally instead of mailing it back.