With the ever-increasing number of web services registered in service communities, many users are apt to find their interested web services through various recommendation techniques, e.g., Collaborative Filtering (i.e., CF)-based recommendation. Generally, CF-based recommendation approaches can work well, when a target user has similar friends or the target services (i.e., services preferred by the target user) have similar services. However, when the available user-service rating data is very sparse, it is possible that a target user has no similar friends and the target services have no similar services; in this situation, traditional CF-based recommendation approaches fail to generate a satisfying recommendation result. In view of this challenge, we combine Social Balance Theory (abbreviated as SBT; e.g., “enemy's enemy is a friend” rule) and CF to put forward a novel data-sparsity tolerant recommendation approach Ser_RecSBT+CF. During the recommendation process, a pruning strategy is adopted to decrease the searching space and improve the recommendation efficiency. Finally, through a set of experiments deployed on a real web service quality dataset WS-DREAM, we validate the feasibility of our proposal in terms of recommendation accuracy, recall and efficiency. The experiment results show that our proposed Ser_RecSBT+CF approach outperforms other up-to-date approaches.