Guaranteeing the availability of Web services is a significant challenge due to unpredictable number of invocation requests the Web services have to handle at a time, as well as the dynamic nature of the Web. The issue becomes even more challenging for composite Web services in the sense that their availability is inevitably affected by corresponding component Web services. Current Quality of Service (QoS)-based selection solutions assume that the QoS of Web services (such as availability) is readily accessible and services with better availability are selected in the composition. Unfortunately, how to real-time maintain the availability information of Web services is largely overlooked. In addition, the performance of these approaches will become questionable when the pool of Web services is large. In this paper, we tackle these problems by exploiting particle filtering-based techniques. In particular, we have developed algorithms to precisely predict the availability of Web services and dynamically maintain a subset of Web services with higher availability. Web services can be always selected from this smaller space, thereby ensuring good performance in service compositions. Our implementation and experimental study demonstrate the feasibility and benefits of the proposed approach.