La aparición de milicias en la Comuna 13 de Medellín se remontan en los años 80´s, cuando grupos de milicianos como las Milicias Populares del Valle de Aburrá, Milicias Metropolitanas, o las Milicias Populares del Pueblo y para el Pueblo, bajo la fachada de ser grupos de autodefensa asesinaban delincuentes y drogadictos, esto con el pretexto de "limpiar las calles" o ejecutar limpieza social de la zona. También en varias zonas de la ciudad el Movimiento 19 de abril llegó a tener campamentos de reclutamiento, con la función de tener una base social.[2][1][3] En varios barrios de Medellín se registraron ataques armados realizados por Escuadrones de la Muerte, el ELN y otras Milicias, sin embargo la mayoría de los delitos no se les dio seguimiento y ni siquiera se pudo establecer al grupo responsable o a los autores.[4][1][5]
Se desconoce la cantidad de personas asesinadas por estos grupos, pero por ejemplo las Milicias Populares del Pueblo y para el Pueblo clamaron haber asesinado a más de 150 miembros.[3][5] Estos grupo comúnmente eran formados por jóvenes de escasos recurso y con poco o nulo trasfondo político, siendo la posibilidad de proteger su comunidad la principal razón para formar parte de las milicias.[6][7]
Para principios de los años 90´s estas milicias perdieron a gran parte de sus líderes, así como parte de apoyo de la población debido a sus actividades de robo, extorsión y narcotráfico en los barrios, inclusive el asesinato de líderes sindicales o estudiantes.[8][1] Bajo esta situación en 1994, en una de las canchas de la Comuna 1650 milicianos de la zona nororiental entregaron sus armas, iniciando así un proceso de desmovilización.[9][10] A pesar de la desmovilización de estas milicias, hubo algunos militantes que no estaban de acuerdo con el proceso de Paz, formando los Comandos Armados del Pueblo.[2][5][11]
La noche del 25 de febrero de 1996, varios exintegrantes de las Milicias Populares, realizaron un “golpe de Estado” a sus líderes y, tras un fuerte enfrentamiento armado ocurrido en el barrio El Salado, asesinaron a cuatro de ellos. Quienes sobrevivieron decidieron plegarse a las órdenes del CAP.[12] Mientras se intensificaba la presencia del grupo, varios informes de los medios colombianos brindaban información aparentemente contradictoria sobre si el CAP es un grupo guerrillero o un nombre utilizado para referirse a varias organizaciones similares.[13] En el contexto de las disputas en la Comuna 13, el grupo llegó a trabajar en conjunto con las fuerzas de las FARC-EP y el ELN que estaban asentadas, pero para finales del 2000, los grupos se enfrentaban entre sí, además de contar con la amenaza de los paramilitares.[11]
Esta milicia tuvo un relativo éxito en la Comuna 13, anteponiendo la acción militar sobre la política, teniendo un enfoque a la autodefensa, publicando comunicados resaltando la "unión de los habitantes", para sobrevivir a los embates de los paramilitares y la fuerza pública.[14][15]