Mientras comandaba las ACCU, Castaño se propuso junto a su amigo Iván Roberto Duque Gaviria alias Ernesto Báez, quien era ideólogo de grupos paramilitares aparecidos en Cundinamarca en la década de 1980, afianzar la unificación de los grupos paramilitares del país en una asociación que se conocería como las Autodefensas Unidas de Colombia (AUC), la cual fue conformada en abril de 1997 y donde Castaño fue nombrado líder.