Родился 10 марта 1941 г. в г. Брад в уезде Хунедоара.
В 1964 г. окончил юридический факультет Бухарестского университета, в 1968 г. - аспирантуру на факультете экономических и социальных наук Женевского Университета.
В 1973 г. получил докторскую степень в области политологии и международного права в Женевском университете и Женевском институте международных отношений и развития.
В 1966 г. начал работать в МИД Румынии. В 1966-1970 гг. был дипломатическим атташе в Управлении по правовым и договорам, в 1970-1978 гг. - третьим секретарем в Департаменте международных организаций.
В 1978-1985 гг. был вторым секретарем Постоянного представительства Румынии при ООН в Женеве.
В 1985 г. вернулся на работу в МИД. В 1985-1990 гг. являлся генеральным секретарем Департамента по вопросам международной безопасности и разоружения в МИД Румынии, в 1990-1991 гг. - госсекретарем по Латинской Америке, Азии и Африке, в 1991-1992 гг. был госсекретарем министра иностранных дел.
В 1992-1996 гг. занимал пост министра иностранных дел в правительстве Николае Вэкэрою.
В 1996-2012 гг. - член сената (верхняя палата парламента) от уезда Прахова. До июня 1997 г. состоял в парламентской фракции Социал-демократической партии Румынии (СДПР).
В 1997 г. основал и возглавил партию "Альянс за Румынию" (АР). В январе 2002 г. произошло слияние АР с Национальной либеральной партией Румынии (НЛПР), а Мелешкану стал первым вице-президентом НЛПР. Состоял в партии до 2012 г.
В 2000 г. был кандидатом на президентских выборах от АР, в первом туре занял седьмое место (1,9%).
В 2007-2008 гг. являлся министром обороны в правительстве Кэлина Попеску-Тэричану. В январе-феврале 2008 г. исполнял обязанности министра юстиции.
В 2012-2014 гг. возглавлял Службу внешней разведки Румынии.
В ноябре 2014 г. вновь баллотировался на пост президента Румынии, в первом туре занят девятое место (1,09%).
10 ноября 2014 г. Мелешкану был назначен министром иностранных дел в правительстве Виктора Понты, сменил на посту Титуса Корлецяна, который подал в отставку из-за плохой организации первого тура президентских выборов. 24 ноября 2014 г. после второго тура президентских выборов, прошедших 16 ноября, Мелешкану подал в отставку по той же причине.
В январе 2016 г. вступил в "Альянс либералов и демократов", от которого на парламентских выборах в декабре 2016 г. был вновь избран в сенат.
В январе 2017 июле 2019 гг. являлся министром иностранных дел в правительстве Сорина Гриндяну.
С 10 сентября 2019 г. возглавляет Сенат Румынии.
Женат, имеет дочь.