Electronic communication of healthcare related information (in the framework of Regional Healthcare Information Networks), introduces a number of security risks with regard to confidentiality, integrity and availability, which can become quite crucial taking into account its sensitive nature. Public Key Infrastructure (PKI) is acknowledged as an appropriate means for dealing with such risks, as long as all the involved critical factors are first practically assessed. This paper presents a best-practice approach for secure regional healthcare networks in Europe, examining all the identified crucial parameters (technical, organisational, legal/regulatory, medical and business). Our approach is conducted at two levels (the regional and the European), including the integration of PKI-aware security mechanisms (strong authentication, encryption, digital signature, time-stamping) in three regional pilot sites in Greece, Finland and Germany and demonstrating their interconnection in a pan-European architecture. Following the above approach, some major conclusions are excluded, pointing out existing open issues and possible steps forward.