Née à Beyrouth, Leila SHAHID a fait des études d'anthropologie et de sociologie à l'université américaine de Beyrouth, un des foyers historiques de la contestation politique palestinienne. Membre du Fatah, le principal mouvement de l'Organisation de libération de la Palestine, marquée par la révolte des camps palestiniens du Liban, en 1969, elle s’engage en politique. En 1989, Yasser Arafat lui propose une mission diplomatique : représenter la Palestine en Irlande, puis en 1990 aux Pays-Bas. En 1994, elle est nommée déléguée générale de Palestine en France, poste qu’elle occupe jusqu’en novembre 2005, date de sa nomination comme déléguée générale de Palestine auprès de l’Union Européenne, de la Belgique et du Luxembourg.