Many countries, European and worldwide, have increasingly issued during the last decade electronically readable identity documents to their citizens, for different purposes and applications. However, a major characteristic of all these systems is that they are basically available in a national context. For example, European citizens that move freely through the Member-States face the problem that their eIDs from their home state do not allow access to services of another Member-State in which they are temporarily present. Public Administrations are also unable to provide services to European citizens from other Member-States with the same ease and efficiency as they do to their national citizens. In order to avoid such confusing situations, cross-border services should be fully integrated in the national/regional and local information systems. It is, therefore, an important task to improve the cross-border interoperability of electronic identification and authentication systems. ENISA, the European agency for the security of computer systems and networks, recently published a report dealing with an important aspect of this problem: the security issues in cross-border electronic authentication. The report assesses the risks of electronic authentication in cross-border solutions and provides a generic implementation model. This paper describes an implementation methodology for addressing the cross-border interoperability of electronic authentication problem, based on the ENISA generic model. The proposed implementation methodology has been based on the successful NETC@RDS project approach and experience, described herein. This methodology can provide a suitable secure cross-border, multi-purpose authentication implementation based on the aforementioned generic model that can be used in various sectors.