Cloud-based healthcare service with the Internet of Healthcare Things (IoHT) is a model for healthcare delivery for urban areas and vulnerable population that utilizes the digital communications and the IoHT to provide flexible opportunities to transform all the health data into workable, personalized health insights, and help attain wellness outside the traditional hospital setting. This model of healthcare Web services acts like a living organism, taking advantage of the opportunities afforded by running in cloud infrastructure to connect patients and providers anywhere and anytime to improve the quality of care, with the IoHT, acting as a central nervous system for this model that measures patients' vital statistics, constantly logging their health data, and report any abnormalities to the relevant healthcare provider. However, it is crucial to preserve the privacy of patients while utilizing this model so as to maintain their satisfaction and trust in the offered services. With the increasing number of cases for privacy breaches of healthcare data, different countries and corporations have issued privacy laws and regulations to define the best practices for the protection of personal health information. The health insurance portability and accountability act and the privacy principles established by the Organization for Economic Cooperation and Development (OECD) are examples of such regulation frameworks. In this paper, we assert that utilizing the cloud-based healthcare services to generate accurate health insights are feasible, while preserving the privacy of the end-users' sensitive health information, which will be residing on a clear form only on his/her own personal gateway. To support this claim, the personal gateways at the end-users' side will act as intermediate nodes (called fog nodes) between the IoHT devices and the cloud-based healthcare services. In such solution, these fog nodes will host a holistic privacy middleware that executes a two-stage concealment process within a distributed data collection protocol that utilizes the hierarchical nature of the IoHT devices. This will unburden the constrained IoHT devices from performing intensive privacy preserving processes. Additionally, the proposed solution complies with one of the common privacy regulation frameworks for fair information practice in a natural and functional way which is OECD privacy principles. We depicted how the proposed approach can be integrated into a scenario related to preserving the privacy of the users' health data that is utilized by a cloud-based healthcare recommender service in order to generate accurate referrals. Our holistic approach induces a straightforward solution with accurate results, which are beneficial to both end-users and service providers.