Abstract: Service composition is a prevalent means to construct service-oriented, loosely-integrated and agile applications. Current service composition technologies are mostly developed for the situations where business requirements are definite and business processes can be predefined. However, there exist many problem-solving cases in which people are not totally clear in advance how to compose applications, but have to act in a try-and-error manner. A novel approach to dealing with the challenge is proposed. Focuses are on the programming model supporting exploratory service composition as well as a dynamic service recommendation mechanism. The proposed approach is evaluated from the users' perspective.