Народився Лінкявічюс 6 січня 1961 року у Вільнюсі, Литовська РСР у сім'ї інженера та вчительки. Дитинство та юність провів у Каунасі.
1978 року із золотою медаллю закінчив 7-у Каунаську середню школу.
У 1978-1983 роках він навчався у Каунаському політехнічному інституті на факультеті автоматики за спеціальністю інженер-електрик. Крім литовської, розмовляє англійською, російською і польською мовами.
Працював секретарем районного комітету ЛКСМ Литовської РСР у Каунасі, завідувачем відділу ЦК ЛКСМ Литовської РСР. Один із ініціаторів та ідеологів відділення литовського комсомолу та створення молодіжного крила соціал-демократичної організації.
З 1990 — кореспондент газети «Tiesa» і консультант парламентської фракції Литовської демократичної партії праці.
У 1991–1996 — член Ради Демократичної партії праці Литви.
У 1992–1996 — депутат Сейму Литовської Республіки.
У 1992–1993 — глава литовської парламентської делегації у Північноатлантичній Асамблеї, заступник голови парламентської комісії зі закордонних справ, голова Молодіжного союзу праці та оглядач газети «Tiesa».
У 1993–1996 — Міністр оборони Литовської Республіки.
У 1997–2000 — Посол, голова представництва Литви в НАТО і Західноєвропейському союзі.
У 2000–2004 — міністр оборони Литовської Республіки.
У 2004–2005 — посол з особливих доручень МЗС Литви.
У 2005–2011 — постійний представник Литви в НАТО та Північноатлантичній раді.
З 2011 — посол з особливих доручень МЗС Литви, одночасно, з 13 вересня 2011 — консультант (на громадських засадах) Прем'єр-міністра Литви Андрюса Кубілюса.
25 червня 2012 Президент Литовської Республіки підписала указ про його призначення Надзвичайним і Повноважним Послом Литви в Білорусі з 24 липня 2012. 7 грудня 2012 звільнений з посади.
7 грудня 2012 — 11 грудня 2020 — міністр закордонних справ Литви.
14 грудня 2013, під час Євромайдану, привіз як подарунок українцям, які стояли на Майдані Незалежності, теплі рукавички, виконані у національному литовському стилі та особисто пішов роздавати їх. Також під час перебування на Майдані зустрівся з лідером партії «Удар» Віталієм Кличком та лідером партії ВО «Свобода» Олегом Тягнибоком.
Послідовно критикував режим Віктора Януковича за зраду європейського вектора розвитку та побиття учасників мирних демонстрацій.
4 квітня 2018 закликав Російську Федерацію звільнити утримуваного в Росії українського режисера Олега Сенцова.
Одружений, дві дочки.
Командор ордена Хреста Вітіса (30 березня 2004);
Командор ордена Великого князя Литовського Гядиминаса (3 лютого 2003);
Орден Трьох зірок 3 класу (Латвія, 12 березня 2001);
Орден Хреста землі Марії 2 класу (Естонія, 2 лютого 2005);
Президентський орден Сяйво (Грузія, 2011).
08.08.2021