Relations between Ethiopia and Sudan were very good following the end of the Ethiopian Civil War, due to the support that the Sudanese government had given to the Ethiopian People's Revolutionary Democratic Front. However, relations were strained for a time following the 26 June 1995 assassination attempt against Egyptian president Hosni Mubarak as he was leaving the OAU summit meeting in Addis Ababa. The subsequent investigation revealed that Sudan was involved in this act, forcing the Ethiopian government to take a series of steps against Sudan that September, which included closing the Sudanese consulate in Gambela, reducing the number of Sudanese embassy staff, and terminating all Sudan Airways and Ethiopian Airlines flights between the two countries. However the start of the Eritrean-Ethiopian War led to Sudan and Ethiopia put this conflict between them and normalizing their relations by November 1999 when president Omar Hassan al-Bashir made a formal visit to Addis Ababa.
Efforts to demarcate the porous boundary with Sudan were delayed by the Second Sudanese Civil War. In May 2008, residents along the western Ethiopian border reportedly discovered that the government had agreed to demarcate this boundary when Sudanese soldiers forced them out of their homes. It was reported that as many as 2,000 people were displaced in the Gambela Region, and the Sudanese army reportedly set fire to two dozen Ethiopian farms and imprisoned 34 people in the Amhara Region. However, Prime Minister Meles Zenawi publicly denied that any Ethiopians had been displaced by this agreement.
As of 2007 Ethiopia shelters 66,980 refugees from Sudan, most of whom live in refugee camps in the Benishangul-Gumuz and Gambela Regions.