Entre 1995 y 1996 diferentes grupos armados fueron registrados ante la Superintendencia de Seguridad y Vigilancia privada bajo la figura de las Convivir. En muchos casos, sus representantes legales o fundadores eran reconocidos paramilitares.
El personal del Departamento de Estado y la Oficina de Política Nacional de Control de Drogas de EE. UU. reciben una “defensa verbal” de las fuerzas de Convivir durante una visita a la base de la Marina de Colombia en Barrancón. Un funcionario les dijo que la misión de las Convivir era “parecida a la de los alguaciles a sueldo o al calvario del Lejano Oeste”. Las Convivir proporcionaron “un medio legítimo de defensa de la agresión externa de las fuerzas guerrilleras”.