Collaborative filtering (CF) methods are widely adopted by existing medical recommendation systems, which can help clinicians perform their work by seeking and recommending appropriate medical advice. However, privacy issue arises in this process as sensitive patient private data are collected by the recommendation server. Recently proposed privacy-preserving collaborative filtering methods, using computation-intensive cryptography techniques or data perturbation techniques are not appropriate in medical online service. The aim of this study is to address the privacy issues in the context of neighborhood-based CF methods by proposing a Privacy Preserving Medical Recommendation (PPMR) algorithm, which can protect patients’ treatment information and demographic information during online recommendation process without compromising recommendation accuracy and efficiency. The proposed algorithm includes two privacy preserving operations: Private Neighbor Selection and Neighborhood-based Differential Privacy Recommendation. Private Neighbor Selection is conducted on the basis of the notion of k-anonymity method, meaning that neighbors are privately selected for the target user according to his/her similarities with others. Neighborhood-based Differential Privacy Recommendation and a differential privacy mechanism are introduced in this operation to enhance the performance of recommendation. Our algorithm is evaluated using the real-world hospital EMRs dataset. Experimental results demonstrate that the proposed method achieves stable recommendation accuracy while providing comprehensive privacy for individual patients.