Para Álvaro Uribe, Venezuela se había convertido en una retaguardia que le permitía a la guerrilla reencaucharse. Denunció la existencia de campamentos al otro lado de la frontera lo que creó una situación de extrema polarización con el entonces presidente Hugo Chávez, y de paso, con Ecuador, cuya soberanía había sido violada por Colombia y con el resto de la región agrupada en Unasur. Con Juan Manuel Santos ya elegido para el periodo 2010-2014, pero sin posesionarse, el conflicto con Venezuela siguió en ascenso.
Álvaro Uribe escribió en sus memorias: «Había estudiado que organizaciones como ETA —el grupo terrorista vasco— continuaron con sus actividades criminales muchos años después de haber perdido el apoyo popular y la mayor parte de su capacidad operativa. Como las FARC, durante muchos años sus cabecillas usaron el territorio francés como refugio. Los funcionarios españoles me dijeron hace poco tiempo que el golpe letal que recibió este grupo se produjo cuando Francia permitió que la Policía española entrara a su territorio para buscar a los terroristas. Poco después, ETA anunció el fin de su campaña armada. Pienso, entonces, que para provocar una cadena de acontecimientos similares que hicieran que las FARC y el ELN cesaran sus actividades armadas, se tendrá que eliminar su capacidad de sentirse cómodas en los países vecinos» (Uribe Vélez, No hay causa perdida, 355).
Las recriminaciones entre ambos gobiernos eran constantes. Hugo Chávez acusaba al Gobierno colombiano de planes desestabilizadores que incluían a grupos paramilitares, y Uribe acusaba a Chávez de ser permisivo con las guerrillas en su territorio. El ambiente entre ambos gobiernos llegó al punto de que se especulaba sobre una posible guerra entre los dos países.
En julio de 2010, con Juan Manuel Santos como presidente electo, Colombia denunció ante la OEA la existencia de campamentos del ELN y las FARC-EP en ese país. El Gobierno exhibió fotos y videos satelitales en los que aparecía el jefe guerrillero Iván Márquez y aseguró que había por lo menos 1.500 insurgentes en territorio venezolano. En respuesta, el Presidente Hugo Chávez rompió relaciones con Colombia y afirmó: «A una guerra con Colombia habría que ir llorando, pero habría que ir. Hago responsable al presidente Uribe, enfermo de odio, porque él se va caminando al basurero de la historia». Uribe terminaba su mandato en medio de una de las peores crisis diplomáticas de la historia.