The project, estimated to cost between $13 billion and $20 billion, dwarfing Chevron's $4 billion Chad-Cameroon pipeline north of Nigeria, will also intensify a war of nerves between Russia and Europe, which is trying to break Moscow's stranglehold on its gas supplies.
The project, which was first mooted in the 1970s, finally got the go-ahead on July 3 when the three African states signed an agreement in Abuja, Nigeria's capital, to start work on the 48-56-inch pipeline.
It is scheduled to be completed by 2015, but there is still a long way to go before construction can begin.
Private sector companies have still to be brought in to help finance the project with the state-owned Nigerian National Petroleum Corp. and Algeria's state-run oil and gas monopoly, Sonatrach.
Nigeria has natural gas reserves estimated at 180 trillion cubic feet, the seventh largest in the world.
But the country, whose long-established oil industry in the Niger Delta has been plagued by insurgents and criminal gangs for years, has not yet been able to fully develop a gas industry.
The pipeline would give those ambitions a boost. It is slated to pump 30 billion cubic meters of gas a year northward from the Niger Delta into Algeria.
There it will link up with Algeria's gas grid, and then be fed into Spain or Italy via two pipelines that run under the Mediterranean.
Two others are under construction, but more may be needed to carry the volumes planned for the trans-Sahara project.
The Europeans want the African gas to loosen their dependency on Russian gas. Moscow has disrupted gas supplies to Europe several times in recent years, often in winter.
This has caused deep anxiety across the European Union, which gets one-quarter of its gas from Russia and is seeking to ensure its future energy security.
The planned capacity of the trans-Sahara pipeline would be sufficient to weaken Russia's grip on Europe.
Russia's state-run energy giant, Gazprom, has countered by reaching an agreement with Nigeria to invest $2.5 billion in Africa's biggest oil and gas sector.
Although the Russians are not directly involved in the trans-Sahara pipeline, their mere presence in Nigeria's gas sector worries the Europeans about possible interference later.
If Gazprom does eventually secure a stake in the trans-Sahara pipeline, it would reinforce the Russians' grip on Europe's gas supply rather than widening Europe's supply base.
Gazprom -- along with Total of France, ENI of Italy and Royal Dutch Shell, which are long-established in Nigeria's oil sector -- has expressed interest in participating in the trans-Sahara project with the Nigerian National Petroleum Corp. and Algeria's Sonatrach.
But there is a more immediate threat to the proposed pipeline. The main Nigerian militant group, the Movement for the Emancipation of Niger Delta, has already threatened to sabotage the project.
The group has already forced severe cutbacks in Nigeria's oil production since it launched its campaign in 2005, from 2.6 million barrels per day in 2006 to 1.7 million now.
The Nigerian government says its military forces will protect the gas fields and the trans-Sahara pipeline they will feed. But so far the armed forces have been unable to crush the militants or the highly organized criminal gangs that steal large amounts of oil every year.
Marauding Tuareg tribal rebels in Niger and al-Qaida groups operating in Algeria and the southern Sahara also pose threats to the planned pipeline that until addressed could delay the project.