En el clima que estaba creando la nueva Constitución y las medidas de sometimiento a la justicia contribuyeron para que se abriera un escenario de negociación con otros grupos.
El proceso constituyente, el fin de la Guerra Fría y el cambio de los paradigmas revolucionarios y comunistas hacia los de la socialdemocracia habían generado discusiones y fisuras en las guerrillas. En el ELN este debate interno generó una ruptura de un grupo minoritario en el que estaban tanto la Corriente de Renovación Socialista (CRS), como exdirigentes de A Luchar y frentes guerrilleros del Caribe.
Rotos los diálogos con la CGSB en Tlaxcala, el Gobierno y la CRS, la cual tenía una presencia sobre todo urbana, intelectual y política, abrieron una mesa de conservaciones en octubre de 1993 luego de mantener acercamientos de manera clandestina. Pese al asesinato de dos de sus voceros en medio de la negociación, las conversaciones continuaron y la CRS dejó las armas el 9 de abril de 1994. Quienes se desmovilizaron y buscaron una integración política a la sociedad no encontraron un contexto favorable: muchos de los exmilitantes, dedicados a la política y al liderazgo social, fueron asesinados o desaparecidos.
Otro proceso de paz de carácter local que se adelantó durante el gobierno de César Gaviria fue con las milicias de Medellín. En 1991 la ciudad alcanzó el mayor pico de violencia de su historia: 6.810 homicidios, lo que significaba 18,7 personas asesinadas cada día, de las cuales 17 eran hombres. La tendencia venía en aumento desde 1980 y durante toda esa década se multiplicó por siete. El 81% de las muertes ocurrieron con armas de fuego.
El clima que estaba creando la nueva Constitución y las medidas de sometimiento a la justicia contribuyeron para que se abriera un escenario de negociación con estos grupos. Las Milicias del Pueblo para el Pueblo dieron el primer paso. El Gobierno, acompañado de la Iglesia católica y organizaciones sociales, dio inicio en febrero de 1994 a un diálogo que se conoció como Acuerdo Final para la Paz y la Convivencia, Gobierno Nacional, departamental y municipal y milicias de Medellín, que se firmó el 26 de mayo de ese año.
Alrededor de 850 milicianos participaron de este pacto. De todos los puntos del Acuerdo, el que tuvo más impacto fue el de la conformación de la Cooperativa de Seguridad y Vigilancia (Coosercom). En total 358 jóvenes fueron dotados de armas, uniformes y medios de transporte. La puesta en marcha de la cooperativa no significó una disminución de la violencia y los índices de homicidio. En menos de dos meses fue asesinado su líder, Pablo García, y los enfrentamientos entre estos y la Policía se intensificaron, así como las denuncias de la población sobre abusos cometidos por los uniformados. La Alcaldía de Medellín pidió volver marcha atrás y en noviembre de 1996 el Gobierno Nacional canceló la licencia de Coosercom. Sin embargo, para entonces el país estaba lleno de este tipo de cooperativas bajo la figura de las Convivir. Las milicias no desaparecieron y, de hecho, hacia finales de la década tomaron un nuevo auge y Medellín se vería envuelta en una guerra urbana.