Information and Communication Technologies (ICTs) play significant roles in the improvement of patient care and the reduction of healthcare cost by facilitating the seamless exchange of vital information among healthcare providers. Thus, clinicians can have easy access to patients' information in a timely manner, medical errors are reduced, and health related records are easily integrated. However, as beneficial as data interoperability is to healthcare, at present, it is largely an unreached goal. This is chiefly because electronic Health Information Systems used within the healthcare organizations have been developed independently with diverse and heterogeneous ICT tools, methods, processes and procedures which result in a large number of heterogeneous and distributed proprietary models for representing and recording patients' information. Consequently, the seamless, effective and meaningful exchange of patients' information is yet to be achieved across healthcare systems. This paper therefore appraises the concepts of interoperability in the context of healthcare, its benefits and its attendant challenges. The paper suggests that the adoption of a standardized healthcare terminology, education strategy, design of useable interfaces for ICT tools, privacy and security issues as well as the connection of legacy systems to the health network are ways of achieving complete interoperability of electronic based Health Information Systems in healthcare.