The Internet has evolved and will only continue to evolve as years go by due to . It houses diverse applications, ranging from online auctioning, banking, networking, and many other types of web applications, most of which are commonly implemented as web services. Due to the flexibility in web services, they can become very complex, and as a result, it is difficult to assure their quality. Rigorous testing is required in order to ensure the quality and correctness of a web service. In this paper, we propose a fault-based combinatorial test generation approach. This approach combines fault-based testing techniques with combinatorial testing techniques in order to expose diverse faults within a web service. We are currently applying this testing methodology to a web service and after obtaining results, will compare it to current web service testing methodologies.