Legacy electronic health record systems were not developed with the level of connectivity expected from them nowadays. Therefore, interoperability weakness inherent in the legacy systems can result in poor patient care and waste of financial resources. Simultaneously, healthcare providers are not yet ready to dispose of them. Large hospitals are also less likely to share their data with external care providers due to economic and political reasons. To overcome the barriers in the effective medical data exchange process, we present a novel hybrid cloud called MedShare, dealing with interoperability issues among disconnected but autonomously functioning healthcare providers. The proposed system architecture and its implementation is based upon: 1) custom data extractors to extract legacy medical data from the three hemodialysis centers under consideration; 2) negotiated and converted to a common data model in each of the private cloud of a provider; 3) indexed patient information using the HashMap technique into the public cloud that operates on private clouds, called a hybrid cloud; and 4) a set of services and tools installed as a coherent environment to exchange information smoothly. This paper enables healthcare professionals to appropriately access and securely share a patient's medical information. MedShare allows the healthcare providers and administrators to maintain the control of their patient data, which is always the primary concern in building a trustworthy environment for exchanging patient information. Medshare effectively addresses primary security and privacy concerns surrounding the deployment of data exchange process by including patient consent and a two-way authorization process.