At a formal ceremony near the border, a Syrian commander told Lebanese troops, "Brothers in arms, so long." The soldiers replied, "So long," reported the Associated Press.
A Lebanese commander then told the Syrians, "Brothers in arms, thank you for your sacrifices." His soldiers repeated, "Thank you for your sacrifices."
After the ceremony, Maj. Gen. Rustom Ghazali, the Syrian intelligence chief in Lebanon, 10 carloads of intelligence agents and the remaining 250 Syrian soldiers crossed the border with a cluster of Lebanese civilians saluting and hundreds of Syrians waving flags.
Syrian forces entered Lebanon in 1976, ostensibly as peacekeepers in Lebanon's year-old civil war. After the war ended in 1990, about 40,000 Syrian troops remained, giving Damascus a decisive say in Lebanese politics, according to the AP.
According to the treaty that ended the civil war, Syrian forces were to leave the country, but for more than a decade, a sizeable contingent of troops patrolled Lebanon. Their presence became a major political issue following the Feb. 14 assassination of former Lebanese Prime Minister Rafik al-Hariri.
International pressure and Lebanese anger over the murder grew into protests against the Syrian deployment and prompted the government in Damascus to agree to a withdrawal. The opposition blamed the assassination on the Lebanese government and its Syrian backers, accusations both have denied.
Thousands of Lebanese demonstrated for days in Beirut to down the pro-Syrian government, and U.N. and U.S. pressure intensified on Damascus until it withdrew its army.
Syria gradually pulled out 14,000 troops over the last two months.
With the troop withdrawal, Lebanese allies in the security services also began to depart. Maj. Gen. Jamil Sayyed, often described as the enforcer of Damascus' policy, announced his resignation Monday, and another top security commander left the country with his family, the AP reported.
Gen. Ali Habib, Syria's chief of staff, said at the departure ceremony that Syrian President Bashar Assad decided to pull out his troops after the Lebanese army had been "rebuilt on sound national foundations and became capable of protecting the state."
Habib emphasized that the troop withdrawal did not mean the end to Syrian-Lebanese ties.
"The relations will continue and become stronger at present and in the future," he said, adding, "anyone who things that the history of people can be eliminated by statements made by this or that state is mistaken."
Lebanese army commander Michel Suleiman also vowed continued cooperation between the two countries.
"Together we shall always remain brothers in arms in the face of the Israeli enemy," he said, according to the AP.
U.N. Secretary-General Kofi Annan has dispatched a team led by Senegalese Brig. Gen. Mouhamadou Kandji to verify Syria's withdrawal in accordance with Security Council resolution 1559.