Ocupó la curul que dejó desierta Álvaro Araújo cuando fue procesado por parapolítica. Este ex senador antioqueño se acogió a sentencia anticipada y la Corte Suprema lo condenó por sus nexos con el Bloque Élmer Cárdenas de las Auc. Algunas de las pruebas clave en el proceso las aportaron los ex jefes paramilitares Éver Veloza, alias 'HH', de los bloques Bananero y Calima; y Freddy Rendón Herrera, alias 'El Alemán', del Élmer Cárdenas.

En julio de 2008, 'HH' habló de los estrechos nexos del ex senador Valencia con el Bloque Élmer Cárdenas. El ex paramilitar aportó copia de un periódico de Urabá en el que se hacía referencia a la labor que desempeñaba Valencia Duque como asesor de Asocomun (Asociación Comunitaria del norte de Urabá y Occidente Córdoba), organización social manejada por Germán Monsalve, hermano de 'El Alemán' y amparada según el testimonio, por el Bloque Élmer Cárdenas. 

Respecto al 'El Alemán', la Corte tuvo en cuenta sus declaraciones sobre las reuniones celebradas entre él y Valencia Duque, los apoyos electorales y económicos otorgados a la campaña de Valencia al Senado en 2006 y el intercambio de correos electrónicos que tuvieron al final de la campaña de 2006 en la que Valencia le pedía entre 100 y 200 millones de pesos.


- Sentencia anticipada a ex senador Valencia Duque por 'parapolítica'
- Fiscalía envía otros 11 expedientes de parapolíticos a la Corte
- 'El Alemán' asegura que financió 23 políticos en todo el país
- La telaraña de los 'paras' en Urabá
- Descargue la sentencia en versión PDF