Interoperability in healthcare is a requirement for effective communication between healthcare facilities to ensure timely access to up-to-date patient information and medical knowledge to facilitate consistent patient care. The lack of interoperability between health information systems reduces the quality of care provided to patients and wastes resources. Numerous government health facilities in Tanzania have implemented various health information systems, such as GoT-HoMIS, Afya Care, and EHMS, locally. These systems store individual patient medical records and have not yet centralized them. Therefore, patient medical records between these health facilities cannot be exchanged and used among themselves. Interoperability will allow different information systems and organizations to work together. The research finds various challenges facing the interoperability of different electronic health record (EHR) systems hosted locally in Tanzanian government hospitals. Looking at various government interoperability initiatives and developing frameworks that can assist in solving interoperability issues for health information systems, and finally developing an appropriate interoperability framework for the government electronic health record (EHR) systems for the Tanzanian government hospitals. It utilised a descriptive research method whereby descriptive statistics analysis was applied in analyzing the collected data. The result of the analysis, shows that ICT infrastructure and organization processes are among the major challenges that affect EHRs interoperability. Hence, based on the challenges observed, an electronic health records interoperability frameworks developed that will be used as guidance in the interoperability of two or more EHRs.