The border between Saudi Arabia and Yemen has long been a source of political dispute, particularly from 1990 — when North Yemen and South Yemen became unified — to 2000, when the two countries signed an agreement. Fighting broke out between border guards in 1994 and again in 1998, when three Yemeni soldiers were killed. The 2000 border treaty eased tensions between the governments, but did not eliminate controversy; Saudi Arabia has decried, and attempted to stanch, the illegal flow of weapons and other goods across
The Saudis have long asserted that a secure border is essential to their efforts to maintain law and order. This claim is not entirely without merit: in a 12-month period from 2002 to 2003, more than 30 Saudi border guards were killed in the border town of Jizan, Saudi Arabia. In May 2003, terrorist attacks in Saudi Arabia attributed to Al Qaeda killed more than 50 people, and the Saudi government vowed to crack down on terrorist infiltration.
In 2003, Saudi Arabia began construction of a concrete pipeline along part of its 1.800 Km border with Yemen. Yemen said the fence violated the 2000. In 2004 Saudi Arabia announced that it was halting construction and that future building along the border would adhere to the 2000 treaty with Yemen.
However, it was reported in October 2006, after plans were revealed of Saudi plans to build another fence along their southern border with Yemen to cut down on the 400,000 illegal immigrants. That fence has made their efforts to prevent the infiltration of revolutionary Islamists. The construction of the wall started in 2008 and it will cost $8.5 billion.