To maximize the economic benefits, a cloud service provider needs to recommend its services to as many users as possible based on the historical user-service quality data. However, when a cloud platform (e.g., Amazon) intends to make a service recommendation decision, considering only its own user-service quality data is insufficient, because a cloud user may invoke services from multiple distributed cloud platforms (e.g., Amazon and IBM). In this situation, it is promising for Amazon to collaborate with other cloud platforms (e.g., IBM) to utilize the integrated data for the service recommendation to improve the recommendation accuracy. However, two challenges are present in the above-mentioned collaboration process, where we attempt to use multi-source data for the service recommendation. First, protecting users’ privacy is challenging when IBM releases its own data to Amazon. Second, the recommendation efficiency and scalability are often low when the user-service quality data of Amazon and IBM update frequently. Considering these challenges, a privacy-preserving and scalable service recommendation approach based on distributed locality-sensitive hashing, i.e., SerRecdistri-LSH , is proposed in this paper to handle the service recommendation in a distributed cloud environment. Extensive experiments on the WS-DREAM data set validate the feasibility of our approach in terms of service recommendation accuracy, scalability, and privacy preservation.