Al tiempo que fracasaron las conversaciones de paz con las guerrillas que no se desmovilizaron durante la constituyente y se empantanaron los procesos de sometimiento a la justicia de algunos narcotraficantes, Cesar Gaviria desarrolló la primera política pública de seguridad del país: la Estrategia Nacional contra la Violencia. Si bien esta permitió algunos cambios en el manejo de la seguridad, no logró consolidar un tratamiento diferenciado de las múltiples violencias y sus particularidades regionales, en un entorno en que el fenómeno paramilitar, la noción del enemigo interno y las prácticas de guerra sucia se mantenían.
Los cambios en la inteligencia de las Fuerzas Armadas fueron significativos y quedaron centralizados bajo la Dirección Nacional de Inteligencia (DINTE). Para hacer operativa la doctrina contra las amenazas a la seguridad nacional, se formalizaron las redes de inteligencia militar que se asimilaron a redes de informantes. Para integrar dichas redes se priorizó la participación de militares en retiro o civiles «con preparación, influencia y dignos de confianza», quienes evitarían asistir a las instalaciones militares. Los intercambios con estos serían secretos.