Nació en Bogotá el 29 de agosto de 1942 en una familia de políticos conservadores incluyendo su padre, Jorge Leyva Urdaneta, fue congresista y ministro. Terminó el colegio en Nueva York, Estados Unidos, donde su familia se exilió después del golpe de estado que le hizo el General Gustavo Rojas Pinilla a Laureano Gómez en junio de 1953, pues Leyva Urdaneta era ministro de obras públicas.
De vuelta en Colombia, estudió derecho en la Universidad Javeriana y luego entró al Partido Conservador, por el que su papá fue candidato presidencial en 1958 y 1962, por fuera del Frente Nacional.
En 1970 Leyva Durán fue secretario del presidente entrante, el conservador Misael Pastrana. Llegó al Concejo de Bogotá en 1974, a la Asamblea de Cundinamarca en 1976 y a la Cámara por Bogotá en 1978.
Hizo su salto al Senado en 1982 con más de 120 mil votos, con el apoyo de los expresidentes conservadores Mariano Ospina Pérez y Pastrana. Y, como senador, apoyó la campaña presidencial de su copartidario Belisario Betancur, que ganó gracias a la ruptura del liberalismo entre las candidaturas de Alfonso López Michelsen y Luis Carlos Galán.
En 1984 renunció al Senado porque Betancur lo nombró Ministro de Minas y Energía, cargo que sólo ocupó por un año y en el que lo reemplazó el liberal Iván Duque Escobar, el padre del después presidente Iván Duque.
Hizo parte de la Comisión Nacional de Verificación durante los diálogos de paz con el ELN, M-19 y Farc que adelantó Betrancur. Aunque las negociaciones no prosperaron, Leyva tuvo un papel importante en el cese al fuego con las Farc que duró de 1984 a 1990, y dio sus primeros pasos en el tema que ha marcado su carrera desde entonces: ser un puente para una salida negociada al conflicto.
En 1986 promovió una fallida consulta popular conservadora para elegir al siguiente candidato presidencial, pero su partido decidió por convención que el candidato sería Álvaro Gómez Hurtado. Gómez perdió las elecciones frente al liberal Virgilio Barco.
Durante el gobierno Barco, Leyva creó la Comisión Promotora de la Política de Reconciliación para facilitar los acercamientos entre el gobierno y las Farc. Y en 1988 fue el principal negociador del gobierno con el M-19 para lograr la liberación de Gómez Hurtado.
Un año después, se presentó como candidato presidencial, pero su partido le dio el aval al empresario vallecaucano Rodrigo Lloreda, quien perdió las elecciones frente al liberal César Gaviria.
A fines de 1990 fue elegido miembro de la Asamblea Constituyente y no por su partido sino por la Alianza Democrática M-19, partido que surgió de la guerrilla después de los acuerdos de paz de 1989 y que incluyó en su lista a la constituyente a varias personas de otros orígenes políticos.
Como constituyente, Leyva participó en el diálogo con la Coordinadora Guerrillera Simón Bolívar, sombrilla de las guerrillas de las Farc, el ELN y el EPL. Estos diálogos de paz finalmente fracasaron en 1992.
Durante el gobierno de Ernesto Samper (1994-1998), Leyva volvió a participar en diálogos con las Farc en el municipio de La Uribe, Meta, que no prosperaron por el escándalo del Proceso 8 mil.
En los últimos años de la década de 1990, fue crucial su participación en la implementación de los Protocolos de los Convenios de Ginebra, parte del derecho internacional humanitario con el objetivo de proteger a los civiles víctimas en conflictos armados. Estos fueron claves en el país porque permitieron aclarar la responsabilidad del Estado y otros actores en el conflicto y facilitó la difusión del DIH en el conflicto. Además, ayudó con la liberación de los militares secuestrados en la base de las Delicias.
En 1997 estalló un escándalo mediático alrededor de Leyva, quien durante conversaciones con paramilitares y guerrilleros que sostuvo con Juan Manuel Santos, terminó viajando en el helicóptero del esmeraldero Víctor Carranza, que era muy cercano a los paramilitares y ayudó a gestionar la reunión de Leyva y Santos con Carlos Castaño y otros 25 miembros de grupos paramilitares y guerrilleros.
En el proceso de paz del gobierno de Andrés Pastrana, Leyva participó en el primer acercamiento entre el gobierno y las Farc. Su participación se detuvo cuando el entonces fiscal general Alfonso Gómez Méndez le abrió una investigación por presunto enriquecimiento ilícito con dinero del Cartel de Cali. Gómez emitió una medida de aseguramiento para capturar a Leyva.
Leyva estaba en Costa Rica y, ante las acusaciones, decidió pedir asilo político en este país, denunciando que era víctima de una persecución política. Aunque la Oficina del Alto Comisionado de las Naciones Unidas para los Refugiados dijo que era un refugiado, la Interpol lo capturó en Madrid en 2002. Estuvo preso dos meses pero fue absuelto por la Corte Suprema de Justicia de Colombia y regresó a Colombia en 2006.
En ese mismo año fue candidato a la presidencia por el Movimiento Nacional de Reconciliación, su movimiento disidente porque el Partido Conservador decidió apoyar la reelección de Álvaro Uribe. Sin embargo, retiró su campaña 20 días antes de las elecciones alegando falta de garantías electorales y la falta de debate. Uribe ganó las elecciones y quedó reelegido como presidente por un segundo período.
Durante la segunda administración de Uribe, Leyva gestionó el acuerdo humanitario con las Farc, este fue aprobado por el Gobierno.
En el escándalo de los computadores del jefe guerrillero Raúl Reyes, que se recuperaron después de la operación en la que fue abatido en 2008, Leyva volvió a estar en la mira pública. Aparecía mencionado en una conversación electrónica entre Reyes, Manuel Marulanda y una persona con el seudónimo “El profe”, que, según analistas de inteligencia, era el mismo Leyva.
Según los correos firmados por “El profe”, si Leyva ganaba la presidencia en 2006 esa guerrilla liberaría a Ingrid Betancourt y él adaptaría su programa de gobierno a lo definido en las conferencias de las Farc.
Aunque la Fiscalía llamó a Leyva a indagatoria por el delito de rebelión, terminó cerrando el proceso porque encontró que los correos sólo mostraban negociaciones en el marco de trabajo de Leyva con el Gobierno, y no había pruebas de que Leyva fuera “El profe”.
Leyva regresó a la palestra pública con los diálogos de paz entre el gobierno de Juan Manuel Santos y las Farc.
En 2015 fue uno de los tres designados por las Farc en una comisión independiente que discutía temas de justicia, con el abogado español Enrique Santiago y el secretario del comité permanente para la defensa de los DDHH, Diego Martínez. Por el gobierno estaban Manuel José Cepeda, Juan Carlos Henao y Douglass Cassel. Uno de los grandes resultados de ese trabajo fue la Justicia Especial para la Paz (JEP).
En 2020, la Fiscalía reconoció que durante su trabajo en la Habana, el celular de Leyva fue interceptado ilegalmente.
En junio de 2022, Leyva fue el primer ministro que anunció Gustavo Petro, que lo designó como Canciller. Leyva anunció que la suya será será “la Cancillería de la Paz” y que entre sus prioridades estará negociar con el ELN.