Telemedicine has increased the number of ways in which healthcare can be delivered across places and countries instead of requiring the provider and the recipient to be present in the same place. One application of telemedicine is the exchange of medical images between remotely located healthcare entities. However, a major obstacle telemedicine faces is providing confidentiality, integrity, and authenticity to transmitted medical images. In this paper, we propose a hybrid algorithm which combines encryption and digital watermarking techniques in order to provide the required authenticity and integrity services. A cryptographic watermark and the patient's data are hidden in the cover image before being transmitted over vulnerable public networks. On the receiver's side, the watermarked image is handled by the extraction procedure in order to extract the cryptographic watermarks and the embedded medical data. The proposed algorithm was tested and evaluated using medical images of two different modalities. The experimental results demonstrate the effectiveness of the proposed algorithm.