The Internet of healthcare things is essentially a new model that changes the way of the delivery and management of healthcare services. It utilizes digital sensors and cloud computing to present a quality healthcare service outside of the classical hospital environment. This resulted in the emergence of a new class of online web 4.0 services, which are termed “cloud healthcare services”. Cloud healthcare services offer a straightforward opportunity for patients to communicate with healthcare professionals and utilize their personal IoHT devices to obtain timely and accurate medical guidance and decisions. The personal IoHT devices integrate sensed health data at a central cloud healthcare service to extract useful health insights for wellness and preventive care strategies. However, the present practices for cloud healthcare services rely on a centralized approach, where patients’ health data are collected and stored on servers, located at remote locations, which might be functioning under data privacy laws somewhat different from the ones applied where the service is running. Promoting a privacy respecting cloud services encourages patients to actively participate in these healthcare services and to routinely provide an accurate and precious health data about themselves. With the emergence of fog computing paradigm, privacy protection can now be enforced at the edge of the patient’s network regardless of the location of service providers. In this paper, a framework for cloud healthcare recommender service is presented. We depicted the personal gateways at the patients’ side act as intermediate nodes (called fog nodes) between IoHT devices and cloud healthcare services. A fog-based middleware will be hosted on these fog nodes for an efficient aggregation of patients generated health data while maintaining the privacy and the confidentiality of their health profiles. The proposed middleware executes a two-stage concealment process that utilizes the hierarchical nature of IoHT devices. This will unburden the constrained IoHT devices from performing intensive privacy preserving processes. At that, the patients will be empowered with a tool to control the privacy of their health data by enabling them to release their health data in a concealed form. The further processing at the cloud healthcare service continues over the concealed data by applying the proposed protocols. The proposed solution was integrated into a scenario related to preserving the privacy of the patients’ health data when utilized by a cloud healthcare recommender service to generate health insights. Our approach induces a straightforward solution with accurate results, which are beneficial to both patients and service providers.