Catalogue services provide the discovery and location mechanisms that allow users and applications to locate data on Grids. Replication is a highly desirable feature in these services, since it provides the scalability and reliability required on large data Grids and is the basis for federating catalogues from different organizations. Grid catalogues are often used to store sensitive data and must have access control mechanisms to protect their data. Replication has to take this security policy into account, making sure that replicated information cannot be abused but allowing some flexibility such as selective replication for the sites depending on the level of trust in them. In this paper we discuss the security requirements and implications of several replication scenarios for Grid catalogues based on experiences gained within the EGEE project. Using the security infrastructure of the EGEE Grid as a basis, we then propose a security architecture for replicated Grid catalogues, which, among other features, supports partial and total replication of the security mechanisms on the master. The implementation of this architecture in the AMGA metadata catalogue of the EGEE project is then described including the application to a complex scenario in a biomedical application. Copyright (C) 2008 John Wiley & Sons, Ltd.