La primera vez que se verifica oficialmente la presencia de paramilitares colombianos operando en Venezuela, es en diciembre de 1997. Siete paramilitares son detenidos en Apure bajo la sospecha de participación en secuestros. Se les encuentran armas de guerra, mapas detallados de la zona y una lista de colaboradores ganaderos y terratenientes. Los capturados declararon haber sido contratados por el general golpista Enrique Medina Gómez, de la GN venezolana. Recibieron 75 millones de pesos para llevar a cabo acciones en Venezuela. Una semana después los paramilitares fueron liberados por orden del mismo general y hasta recibieron salvoconductos firmados por él. En 2002 Medina Gómez participó en el golpe de Estado y las actividades de la ultraderecha golpista en Plaza Altamira.

Carlos Castaño, declaró en 1997 haberse reunido con 140 empresarios, ganaderos y terratenientes de Barinas, Táchira y Zulia, con miras a construir una estructura paramilitar en esos estados.

El 15 de julio de 2000, una docena de personas fuertemente armadas secuestraron en Carabobo, al empresario Richard Boulton. Las investigaciones dieron lugar a diversos allanamientos y detenciones de paramiitares colombianos en San Cristóbal, Maracay y Valencia. Sin embargo, Richard Boulton no fue liberado hasta el 15 de julio de 2002, por mediación de Carlos Castaño , quien declaró que los secuestradores pertenecían a una supuesta facción disidente de la AUC. Obviamente eso no se pudo confirmar.

El 26 de junio de 2002, varios medios difundieron un video en el cual unas supuestas Autodefensas Unidas de Venezuela declararon operar en Táchira, Apure y Zulia. Un “Comandante Antonio”, dijo que reunían 2.200 hombres armados, declaró al presidente Hugo Chávez como objetivo militar y anunció que iban a cambiar el panorama político de Venezuela. Unos días después, Carlos Castaño admitió: “Tenemos gente dictando instrucción en territorio venezolano. Mantenemos comunicación. Es un proceso de gestación.

Sin embargo, en 2003 las AUC desarrollaron varias incursiones militares y ataques a territorio venezolano desde Colombia. El 19 de marzo aproximadamente 500 paramilitares cruzaron el límite fronterizo natural Rio de Oro (Sierra d Perijá, Zulia) con uniformes nuevos, armas de guerra y equipos de comunicación modernos. Asaltaron y saquearon el pueblito venezolano La Escuelita, portando insignias de las tropas colombianas de contrainsurgencia, el ELN y la GN venezolana.
El 4 de septiembre el Ejercito venezolano fue atacado por paramilitares colombianos en el municipio Ayacucho (Táchira ) a seis kilómetros de la frontera.

El 5 de septiembre murieron tres paramilitares colombianos y un soldado venezolano quedó gravemente herido en un enfrentamiento en la zona fronteriza del Táchira.

Después de 2003, ocurrieron enfrentamientos esporádicos. La estrategia se concentró más bien en construir y consolidar estructuras paramilitares en el interior de Venezuela sin llamar demasiado la atención.

Un personaje importante en las tramas contrarrevolucionarias y nexos con la AUC , fue el ex general de la GN Felipe Rodríguez, alías “El Cuervo”. Rodríguez tuvo un rol central en el golpe de 2002, luego fue jefe de seguridad de Plaza Francia en Altamira (Caracas), durante la ocupación de la misma por militares y ex militares golpistas. Luego fue prófugo de la justicia, que lo buscaba como partícipe del golpe y presunto autor de unos atentados explosivos contra las embajadas de Colombia y España en el 2003. Rodríguez fue capturado, fuertemente amado, el 5 de febrero de 2005 en Caracas, y fue condenado en abril de 2008, a 10 años y 6 meses de reclusión, por su participación en los atentados contra las embajadas.
Los contrarrevolucionarios venezolanos también tienen lazos estrechos con el sector terrorista cubano de EEUU., donde hasta tienen la posibilidad de entrenar tranquilamente en su lucha terrorista. The Wall Street Journal, en su editorial del 29 de enero de 2003 rinde cuenta de unos campos de entrenamiento de terrorista en Florida.

El caso más espectacular de infiltración paramilitar hasta la fecha fue la detención de casi 130 paramilitares colombianos en la finca Daktarí en Baruta, cerca de Caracas, en mayo de 2004, con la finalidad de asesinar a Chávez y crear una gran confusión en Venezuela. Esto se abortó por la infiltración de un agente de la Disip. Un coronel de la Aviación propuso bombardear con F-16 el Aló Presidente. El despegue del n F-16 iba a dar la señal de ejecución del plan. Los paramilitares-vestidos con uniformes del Ejército venezolano-iban a bloquear el comando de la Guardia Nacional y atacar el Palacio de Miraflores.

La finca donde se encontraron los paramilitares pertenecía a Robert Alonso, un exilado cubano, hoy prófugo en Florida., y los paramilitares tenían uniformes de las Fuerzas Armadas de Venezuela. Entre los detenidos estaba el jefe del grupo, José Ernesto Ayala Amado, alias “Comandante Lucas”, del Bloque Norte de Santander de las AUC. Según sus declaraciones, había entrado al país a mediados de abril siguiendo las instrucciones del empresario venezolano Gustavo Zingg Machado.

Lucas declaró sobre la participación de políticos de oposición del Zulia, federaciones de ganaderos, la Onidex de San Antonio del Táchira, del animador Orlando Urdaneta. Según la Disip estuvieron involucrados también Pedro Carmona Estanga, ex dirigente empresarial y golpista autoproclamado presidente en abril 2002; María Luisa Choisone, directora ejecutiva del Bloque de Prensa Venezolana; Liliana Hernández, diputada de Primero Justicias, Rafael Marín, ex secretario general de AD; Ovidio Poggioli, ex director del Aeropuerto Internacional Simón Bolívar.
Un gran negocio de los paramilitares colombianos en la zona fronteriza desde hace muchos años el contrabando de gasolina de Venezuela hacia Colombia, donde la gasolina cuesta más de 30 veces. El contrabando está en gran parte bajo control paramilitar, ya que también la usan para la producción de cocaína.

A finales de 2007 se podía observar en todas las tiendas de la Costa Atlántica de Colombia mayoritariamente alimentos venezolanos de contrabando. A finales de 2007, en Ureña y San Antonio los paramilitares, en algunos barrios(por ejemplo cerca del aeropuerto), estaban cobrando cinco bolívares fuertes por casa para “limpieza social”. A fines de de 2008 la policía del Táchira capturo cuatro presuntos paramilitares del frente Puerto Santander (Colombia) en la Fría municipio García Hevia. El 24 de abril de 2))8 efectivos de las Fuerzas Armadas descubrieron cerca de Boca de Orope, en en el municipio Catatumbo, en la Sierra de Perijá, estado Zulia, un campamento de paramilitares colombianos a 500 metros de la frontera. Según informaciones de autoridades militares. Otra de las actividades de los “paracos” es controlar el tráfico de drogas en la región y sobre todo el lavado de dinero del narcotráfico, especialmente a través de las operaciones inmobiliarias.

La penetración paramilitar en la capital es ya bastante avanzada, especialmente en los barrios(con mayor presencia en Petare, El Valle, Coche y la zona del Cementerio). Los asesinatos de activistas de base en los barrios de Caracas y otras zonas del país han aumentado en forma preocupante, como lo reportan muchas organizaciones populares y algunos autores. Sin embargo, pasan desapercibidos a causa de su dimensión local.

Una estrategia, implementada desde el 2005, fue acercarse a los pequeños criminales de barrio y regalarles cocaína o vendérsela a un precio muy bajo del precio del mercado para establecer nexos. Después de haber creado un nexo y haber hecho unos cuantos negocios favorables para los pequeños criminales, se les piden “favores”, como por ejemplo matar a ciertas personas.

El primero de mayo de 2008 aporrea.org publicó una denuncia de habitantes del bloque 5 de Las Lomas de Urdaneta, en Catia, Caracas. El jueves 14 de febrero d 2008, como informó el mismo presidente Chávez, en Plaza Venezuela (Caracas) fueron capturados varios supuestos paramilitares colombianos.