This paper aims to contribute to the literature on how European foreign policy works in practice by focusing on the issue of recognition. Recognition is a gradual process, more than a black-or-white phenomenon and the paper articulates different steps in the process. It then turns to analyse the specific case of the Arab-Israeli conflict and how European countries address the various actors. The evidence shows that EU member states have all recognised the key role of the PLO and have recognised or are very close to the recognition of Palestine, but have maintained only the most basic form of recognition (or misrecognition) of Hamas. In parallel, member states have retracted recognition to Israeli settlements in the West Bank, although the process has been slow and fragmented, as well as shrouded in technicalities.