En abril de 1989 el presidente Virgilio Barco prohibió las autodefensas que habían sido promovidas desde 1965 y que tenían al país bañado en sangre. Pero la prohibición no fue suficiente. En agosto los paramilitares del Magdalena Medio asesinaron al que se perfilaba como futuro presidente de Colombia: Luis Carlos Galán.
En ese momento, Gonzalo Rodríguez Gacha (El Mexicano) se convirtió en el principal objetivo del Gobierno. En diciembre de ese año murió en un enfrentamiento con la Policía. Lo había vendido el Cartel de Cali, que había infiltrado a uno de sus hombres, conocido como El Navegante, en su círculo cercano en Tolú, Sucre, donde se escondía. Rodríguez Gacha era el financiador principal de las autodefensas de Puerto Boyacá y la conexión de estas con el Cartel de Medellín.
Luego de su muerte, Escobar amenazó a los líderes de esta agrupación, Henry Pérez y Ramón Isaza, para que se unieran a una guerra contra el Estado, pero estos no cedieron porque la consideraban contraria a su guerra antisubversiva. Tampoco estaban dispuestos a pelear una guerra ajena, menos ahora que el Estado los estaba persiguiendo tras encontrar que miembros de la organización habían participado en el asesinato de Luis Carlos Galán.