Complexity metrics are useful for predicting the quality of software systems because they quantify the quality attributes. Web services, a new kind of software system has been providing a common standard mechanism for interoperable integration of disparate systems and gaining a great deal of acceptance by different types of parties that are connected to the internet for different purposes. In this respect, quality of the web-services should be quantified for easy maintenance and quality of services. Further, the Web Services Description Language (WSDL) forms the basis for Web Services. In this paper, we are evaluating the quality of the WSDL documents by applying the Cyclomatic Complexity metric, a well known and effective complexity metric, which has not been used to evaluate the quality of WSDL till date.