La víspera de la navidad de 2002 el presidente Álvaro Uribe sancionó la Ley que le permitía abrir negociaciones con las Autodefensas Unidas de Colombia (AUC), una de sus primeras iniciativas de Gobierno. Con esa firma resolvía, aparentemente, el dilema que habían enfrentado sus antecesores, desde los años ochenta, sobre el tratamiento que debería dársele a los grupos paramilitares. En términos reales, no solo no se les había perseguido ni militar, ni judicial ni políticamente, sino que durante los años noventa lograron consolidar un entramado al que concurrió buena parte de la clase política y sectores económicos.
Para Estados Unidos los paramilitares eran claramente narcotraficantes. En una tardía decisión, el 10 de septiembre de 2001, justo la víspera del ataque a las Torres Gemelas en Nueva York, el Departamento de Estado de los Estados Unidos afirmó que «las AUC dejaron de ser una organización que simplemente aprovechaba los “impuestos” y el transporte de la droga, y se convirtieron en una organización “implicada en toda la cadena del narcotráfico”» (Cable, U. S. Departament of State, «Colombia: Country Reports on Human Rights Practices 2002», Washington, 31 de marzo de 2003 (citado en International Crisis Group, «Colombia: Negociar con los paramilitares»).
Si bien era cierto que estos grupos nacieron, crecieron y actuaron de la mano del Estado, también lo era que tenían bastante autonomía, particularmente porque desde su expansión en 1997 los narcotraficantes le habían inyectado grandes sumas de dinero a las AUC, a cambio del dominio sobre rutas para producir y exportar cocaína. No obstante, el Gobierno les daba tratamiento político.