The article analyses how the Europeans (meaning European states and the EC/EU) have progressively turned a discourse about the Israeli-Palestinian border into a foreign policy practice. While much of the literature highlights the existence of a ‘gap between discourse and practice’ when it comes to Europeans’ foreign policy stance towards the Arab-Israeli conflict, we argue that the gap is dynamic and has changed across time. In the absence of an internationally and locally recognised border between Israel and Palestine, the Europeans have aimed at constructing one on the 1949 armistice line, the so-called Green Line. They have done so in stages, by first formulating a discursive practice about the need for a border, then establishing economic practices in the late 1980s-early 1990s, and most recently practicing a legal frame of reference for relations with Israel and the Palestinian Authority (PA) based on the Green Line. The outcome is that, for what concerns European countries and EU legislation, the Green Line has been increasingly taken as the Israeli-Palestinian border. However, gaps never fully close and more contemporary events seem in fact to point to a re-opening of the gap, as the article explores.