In 2001, President Andrés Pastrana Arango appointed him Ambassador of Colombia to Italy with dual accreditation to Greece, Malta, San Marino, Cyprus, and the United Nations' agencies in Rome.

[1] As Ambassador of Colombia to Italy, Cassio was dually accredited as Non-Resident Ambassador to San Marino, and Malta, and as Permanent Representative the specialized organizations of the United Nations with headquarters in Rome (the Food and Agriculture Organization, the World Food Programme, and the International Fund for Agricultural Development).

Valencia presented his Letters of Credence to President of Malta Guido de Marco on 18 October 2001 at the San Anton Palace in Valletta.

[3] On 2 June 2005, in recognition of Valencia's meritorious labor as Ambassador to Italy, he awarded the Order of Merit of the Italian Republic in the category of Knight Grand Cross by President Ciampi; he was presented the honor on 20 December by the Resident Ambassador of Italy to Colombia, Antonio Tarelli at the Italian Embassy in Bogotá.

[4] On 20 June 2008, President Álvaro Uribe Vélez named Valencia to succeed Carlos Holguín Sardi as Minister of the Interior and Justice of Colombia.