With the popularity of Service-Oriented Computing, how to construct highly available service-oriented applications is becoming a hot topic in both the research and industry communities. As a fundamental problem in dynamic service selection, availability estimation is challenging because of the dynamic nature of web services. To grasp the dynamic nature of web services, we set up an experimental environment for collecting runtime information of web services. Based on the collected runtime information, we identify several characteristics of service failures and successes, and further define three typical service runtime statuses. Based on these statuses, we propose a novel approach to dynamic availability estimation, which is called Status Identification based Availability Estimation for Service Selection(SIBE). To evaluate our approach, we compare SIBE with other approaches in an experiment of dynamic service selection on the Internet. Experimental results show that SIBE can efficiently improve the success rate of selecting available services.