This article discusses the interoperability of police databases in the EU with reference to the 24 November 2005 Communication from the Commission to the Council and the European Parliament on improved effectiveness, enhanced interoperability and synergies among European databases in the area of Justice and Home Affairs. The different levels of interoperability are identified. Straightforward interoperability within the EU is distinguished from four more controversial levels of interoperability, such as interoperability with atypical systems and interoperability with systems outside the EU. On the basis of this analysis the question of the desirability and suitability interoperability is addressed, followed by a discussion of the necessary guarantees to be included. Contrary to what is often suggested, interoperability is a highly sensitive political issue. The attempt of the Commission's 2005 Communication, to make it look like a mere technical issue does not create the right context for a serious and in-depth discussion.