The taxonomy of Web Service fault is the premise of effective Web service fault diagnosis. Based on the analysis of Web service fault management flow, a new fault taxonomy for web service according to types of service and procedure of service is proposed, and a Web service fault tree is composed. A Web service fault matrix based on the relationship between fault and its symptom is also constructed, which could help diagnose the Web service fault quickly and correctly.