The territorial dispute with neighboring Venezuela--Colombia's traditional rival--appeared to pose a greater possibility for armed conflict than the claims to the island chain off the Nicaraguan coast. During the late 1980s, this dispute with Venezuela was exacerbated by problemÍÍÍÍs over other issues related to the countries' shared border. As a result, the prospects for cooperation in resolving the territorial claims were conditioned by the element of national prestige that was introduced into nearly all bilateral contacts. Other issues that heightened nationalistic concerns included armed clashes following incursions of Colombian-based drug traffickers and guerrillas into Venezuelan territory, as well as reports of civilian casualties caused by Venezuelan troops that entered Colombian territory in hot pursuit. In addition, an almost continuous influx of undocumented Colombian migrants into Venezuela in search of work had begun during the 1970s and continued into the late 1980s. This influx of migrant workers also contributed to heightened tensions between the two countries.

The territorial dispute centered on control over the entrance to the Golfo de Venezuela. The key to establishing this control was ownership of the Islas Los Monjes, a chain of three tiny islands lying at the gulf's northern mouth. At stake in the dispute was the control over a substantial amount of maritime territory in the Caribbean that extended into the gulf, an area popularly referred to by Colombians as the Golfo de Coquibacoa. By gaining recognition of its claim to the islands, which were said to be all but submerged at high tide, Colombia could expand national territory into the Caribbean by declaring the extension of its 200-nautical-mile Exclusive Economic Zone around the islands. It would also be able to claim a portion of the waters of the gulf--located next to Venezuela's oil-rich Lago de Maracaibo--which, according to estimates of possible reserves, might contain as much as 10 billion barrels of oil.

Under an 1842 boundary agreement known as the Pombo-Romero Treaty, Venezuela had ceded its claim to the Guajira Peninsula. Conflicting boundary claims between the two nations remained, however, and the issue became more complex. In 1891 King Alfonso XII of Spain, who had been asked to arbitrate, awarded some portions of the disputed territory to Colombia and others to Venezuela. The Spanish arbitration did not, however, delineate the actual boundaries along the entirety of the shared frontier. The 1941 Treaty on Border Demarcation and Navigation of Common Rivers (also known as the Santos-López Contreras Treaty) presumably settled the dispute by delineating with geographic precision the boundaries along the length of the land border. As a result, most of the Guajira Peninsula remained under Colombian control, but uncertainty continued regarding the extension of the maritime boundary into the gulf.

Following the reestablishment of relative domestic peace in Colombia during the 1960s, the dispute over the islands again became a national issue. Several unsuccessful rounds of 413 negotiaiations were conducted during the 1970s and 1980s. In August 1987, Colombian warships (including the missile frigate Caldas) entered disputed waters at the mouth of the gulf, Colombian Mirage fighters reportedly conducted overflights of the area, and Venezuelan F-16 fighters were moved to a nearby air base. Open hostilities appeared imminent. Even after the withdrawal of the Colombian vessels by order of President Virgilio Barco Vargas, the armed forces of both nations remained on alert in the border area. The Venezuelan government maintained that the vessels' presence in the gulf for three full days represented an act of "intentional provocation" and sent a "strongly worded" formal protest to the Colombian president.

Data as of December 1988