The EU can and should contribute to reforms in the non-EU Mediterranean countries and to the resolution of the Arab-Israeli conflict. For that purpose it must position itself as a normative power. Such a status presupposes, however, legitimacy, which is lacking, to a large extent, in the eyes of Israelis. An attempt is made in this article to offer a theoretically informed, yet empirically grounded analysis of the legitimacy deficit from which the EU suffers, presented through an Israeli prism, coupled with concrete proposals aimed at ameliorating this state of affairs.