Within the European Agenda on Security, interoperability has passed from being a management concept to an encompassing policy goal, achieved through integration of sensor networks with IT databases. This move may trigger a huge impact on the economics of border protection, particularly in the context of maritime surveillance. This paper deals with the opportunities and challenges linked to the search for enhanced interoperability in EU border policy, unpacking the trade-off between the policy goal of attaining the highest-possible threshold of ‘flexiciency‘ and the legal obligation to ensure consistency with the principle of solidarity and fundamental rights protection. It contends that the quest for interoperability is leading to an evolution of EU anticipatory border governance, as based upon pre-emption and extra-territorialisation.