In recent years, various national medical databases have been set up in the EU from disparate local databases and file systems. Medical records contain personal data and are as such protected by EU and member states’ legislation. Medical data, in addition to being personal data, is also defined in the EU legislation as being especially sensitive and warrants special measures to protect it. It therefore follows that various legal issues and concerns arise in connection with these processes. Such issues relate to the merits of compiling a nationwide database, deciding on who has access to such a database, legitimate uses of medical data held, protection of medical data, and subject access rights amongst others. This chapter examines some of these issues and argues that such databases are inevitable due to technological change; however there are major legal and information security caveats that have to be addressed. Many of these caveats have not yet been resolved satisfactorily, hence making medical databases that already exist problematic.