With the ever-increasing volume of services registered in various web communities, it becomes a challenging task to find the web services that a target user is really interested in from the massive candidates. In this situation, Collaborative Filtering (i.e., CF) technique is introduced to alleviate the heavy burden on the service selection decisions of target users. However, present CF-based recommendation approaches often assume that the recommendation bases, i.e., historical service quality data are centralized, without considering the distributed service recommendation scenarios where data are multi-sourced. Furthermore, distributed service recommendation calls for the collaborations among multiple involved parties, during which the private information of users may be exposed. In view of these challenges, we propose a novel privacy-preserving distributed service recommendation approach based on two-phase Locality-Sensitive Hashing (LSH), named SerRectwo-LSH, in this paper. Concretely, in SerRectwo-LSH, we first look for the “similar friends” of a target user through a privacy-preserving two-phase LSH process; afterwards, we determine the services preferred by the “similar friends” of the target user, and then recommend them to the target user. Finally, through a set of experiments conducted on a real distributed service quality dataset WS-DREAM, we validate the feasibility of our proposal in terms of recommendation accuracy and efficiency while guaranteeing privacy-preservation.