Born in the Estonian capital Tallinn in 1972, he graduated from the prestigious Moscow State Institute of International Relations (MGIMO) and served in the Tokyo embassy.
Tallinnassa vuonna 1972 syntynyt Vaino valmistui arvostetusta Moskovan valtiollisesta kansainvälisten suhteiden instituutista (MGIMO) ja on työskennellyt aiemmin Tokion suurlähetystössä.