Nació el 23 de marzo de 1948. Fue criado en el barrio Aranjuez, uno de los más populosos sectores de Medellín, y creció en una familia modesta, junto con 11 hermanos, de los cuales sobrevivieron diez.

Está casado con la sicóloga María Isabel González y es padre de Juan Camilo, Catalina María, Luis Eduardo y Santiago Valencia González.

En 1970, cuando contaba con 22 años de edad, se inició en la política, colaborando en Antioquia con la campaña presidencial de Misael Pastrana Borrero. Poco después fue Secretario General del Partido Conservador en su departamento, al tiempo que se graduaba de abogado en la Universidad de Antioquia.

En 1974 viajó a Bogotá para trabajar en el entonces llamado Instituto de Crédito Territorial, donde estuvo hasta 1981, cuando llegó a la Secretaría General del Conservatismo y fue elegido Representante a la Cámara el año siguiente. Para 1984 ya era Vicepresidente del partido y en 1986 fue reelegido al Congreso.

En las elecciones de 1991, luego de dos periodos como Representante a la Cámara, Fabio Valencia Cossio llegó por primera vez al Senado. Allí fue ponente de importantes proyectos de ley, entre los que se destaca el de la Ley 100 de Seguridad Social y la Reforma de la Policía Nacional.

En 1994, fue reelegido en el Senado con la segunda votación del país y la primera en el Conservatismo. También fue Presidente del Partido Conservador y Primer Vicepresidente del Senado de la República.

En la Convención Nacional Conservadora de 1996, Valencia Cossio obtuvo la mayor votación y fue elegido Presidente del Directorio Nacional de Partido, cargo que ocupó hasta mediados de 1997.

En las elecciones del 8 de marzo de 1998, fue reelecto senador para el periodo 1998-2002, con la votación más alta del Conservatismo y la segunda a nivel nacional. Así mismo, fue elegido como Presidente del Congreso para el periodo 1998-1999.

En septiembre de 1999 renunció a su curul en el Senado de la República y fue designado por el Gobierno Nacional del entonces Presidente Andrés Pastrana Arango como Negociador en el proceso de paz con las Farc.

Ha sido Embajador Extraordinario y Plenipotenciario de Colombia ante el Gobierno de Italia, Embajador No Residente ante los estados de Grecia, Chipre, Malta y San Marino, y Representante Permanente ante los Organismos Especializados de las Naciones Unidas en Roma (FAO, FIDA Y PMA).

A su regreso de la Embajada de Italia, el Presidente de la República, Álvaro Uribe Vélez, lo nombró Alto Consejero Presidencial para la Competitividad y Comisionado Presidencial de Colombia ante el Plan Puebla Panamá, cargos que deja para ocupar el Ministerio del Interior y de Justicia.

Valencia Cossio es autor de los libros ‘Hacia un Nuevo Municipio’ (1985); ‘Crónicas del Coraje’ (1994); ‘Asia: El Futuro’ (1996) y ‘Fórmulas para salvar a Colombia’ (1996). También es coautor de ‘Libertad de Prensa en Colombia’, ‘Soluciones para el campo’ e ‘Inseguridad e impunidad en Colombia’, entre otros.