With the help of patients’ health data, e-Healthcare providers can offer reliable data service for better medical treatment. For example, clinical pathway provides an optimal detailed guidance for the clinical treatment. However, the e-Healthcare providers are incompetent with the huge volumes of e-Healthcare data, and a popular and feasible solution is used to outsource the medical data to powerful cloud servers. Because the medical data are very sensitive yet the outsourced servers are not fully trusted, the straightforward execution of clinical pathway query service will inevitably bring huge privacy risks to patients’ data. Apart from the privacy issues, the efficiency issues also need to be taken into consideration such as the communication overhead and computational cost between servers and providers. Considering the above issues, this paper proposes a Privacy-Preserving Optimization of Clinical Pathway Query scheme (PPO-CPQ) to achieve the secure clinical pathway query under e-Healthcare cloud servers without revealing neither the private information of patients such as name, gender, age and physical index, nor the sensitive information of hospitals such as treatment, medication and expense. In our proposed scheme, it first designs secure and privacy-preserving several sub-protocols, such as privacy-preserving comparison, privacy-preserving clinical comparison, privacy-preserving stage selection and privacy-preserving stage update protocol, to ensure the privacy in e-Healthcare system, then it adopts the greedy algorithm with a secure manner to perform the query and the Min-Heap technology to improve the efficiency. Experimental result shows that our scheme is practical and efficient in terms of computational cost and communication overhead.