With the advances of data mining and the pervasiveness of cloud computing, online medical diagnosis service has been extensively applied in e-heathcare field, and brought great conveniences to people’s life. However, due to the insufficient data sharing among healthcare centers under the security and privacy concerns of medical information, the flourish of online medical diagnosis service still faces many severe challenges including diagnostic accuracy issues. In this paper, in order to address the security issues and improve the accuracy of online medical diagnosis service, we propose a new privacy-preserving collaborative model learning scheme with skyline computation, called PCML. With PCML, healthcare centers can securely learn a global diagnosis model with their local diagnosis models in the assistance of cloud, and the sensitive medical data of each healthcare center is well protected. Specifically, with a secure multi-party vector comparison algorithm (SMVC), all local diagnosis models are encrypted by their owners before being sent to the cloud, and can be directly operated without decryption. Detailed security analysis shows that PCML can resist security threats in the semi-honest model. Moreover, PCML is implemented with medical datasets from UCI machine learning repository, and extensive simulation results demonstrate that PCML is efficient and can be implemented effectively.