Selecting quality services over the Internet is tedious because it requires looking up of potential services, and yet the qualities of these services may evolve with time. Existing techniques have not studied the contextual effect of service composition with a view to selecting better member services to lower such overhead. In this paper, we propose a new dynamic service selection technique based on perceived successful invocations of individual services. We associate every service with an average perceived failure rate, and select a service into a candidate pool for a service consumer inversely proportional to such averages. The service consumer further selects a service from the candidate pool according to the relative chances of perceived successful counts based on its local invocation history. A member service will also receive the perception of failed or successful invocations to maintain its perceived failure rate. The experimental results show that our proposal significantly outperforms (in terms of service failure rates) a technique which only uses consumer-side information for service selection.