Gibraltar provided the first outcome of the Brexit referendum with 96% voting against it in June 2016. This outcome, together with the impact of the exit of the UK from the European Union, recently brought the attention of the British media to this part of the Mediterranean. Other countries with border issues that will be affected by Brexit obviously include the Republic of Ireland, and the Republic of Cyprus, if we take into consideration the British bases in the Republic of Cyprus Akrotiri and Dhekelia. Gibraltar, like other British Overseas Territories, is of strategic importance for both the current and for a post-Brexit British Foreign Policy. The British bases in Cyprus for example are also of considerable geopolitical importance especially considering that Cyprus is not a member of NATO, but Spain joined the North-Atlantic Alliance in 1982 during the negotiations of its membership to the EU (European Community at that time). However, there are several issues of mainly a political nature that places Gibraltar in an exceptional situation. The discussion over Gibraltar between the UK and Spain started with the Utrecht Treaty in 1713 when the disagreement over the sovereignty of the isthmus took place. Since then, and ongoing during the 20th century, other events such as the development of the airport over territory that is considered by Spain to be their own, has added another layer to this long-standing problem.