Vilnai was born in Jerusalem in 1944. His father was Prof. Zev Vilnay, a pioneer in the sphere of Israeli geography and Land of Israel studies, from whom he inherited a love of nature and hiking. He was drafted into the Israel Defense Forces in 1966, serving in the Paratroopers Brigade and the elite reconnaissance unit Sayeret Matkal. He was deputy commander  of the assault force in Operation Thunderbolt, also known as the Entebbe Raid, to free Jewish and Israeli passengers taken hostage by Palestinian and German terrorists after their Air France plane was hijacked to Entebbe, Uganda. Vilanai led the assault team into the airport building, while another team secured the outside. As a major general, Vilnai was the head of the Manpower Directorate, as well as the Deputy Chief of Staff.
He re-entered the Knesset after the 2003 elections second on Labor's list, but lost his ministerial post as Sharon formed a right-wing coalition that excluded Labor. However, when several parties left the coalition in the face of the disengagement plan, Labor was invited into the government in January 2005. Vilnai was initially appointed Minister in the Prime Minister's Office. In August 2005 he was appointed Acting Minister of Science and Technology, and the post was made permanent in November.
After Ehud Barak won the party leadership election in 2007 he appointed Vilnai as Deputy Minister of Defense. In February 2008, Vilnai threatened that GazanPalestinians "will bring upon themselves a bigger 'shoah' because we will use all our might to defend ourselves." The word shoah (שואה), literally "disaster", is used in Israel to refer to the holocaust.
Vilnai won sixth place on the Labor list for the 2009 elections, and retained his seat in the subsequent election. In 2011 he was one of the five members to leave the Labor Party to establish Independence, and was appointed to the newly created post of Minister for the Home Front, having originally been made Minister of Minorities. In February 2012 Vilnai was appointed Israel's ambassador to China, a move said to be related to Israeli anxiety over Iran's nuclear program. His Knesset seat was taken by Shachiv Shnaan.