[1][2] The long-running dispute arose from the 1934 Treaty of Taif between Yemen and the newly-formed Saudi Arabia and the subsequent demarcation of the boundary three years later.

[3] However, progress would stall over the next three years, in part as the nations contested the exact placement of the maritime portion of the border as it met the Red Sea.

[4] In May 2000, Crown Prince Abdullah of Saudi Arabia attended Yemen for the first time to commemorate the tenth anniversary of the Yemeni unification.

Shortly after this meeting, and a series of intensive diplomatic talks, the two governments finally signed the Treaty of Jeddah in the Saudi port city on 12 June 2000 to take effect the following month.

[2][5] In 2003, Saudi Arabia began construction of a border wall with Yemen citing organised smuggling and security concerns.