Quality of Service (QoS) support in web services plays a great role for the success of this emerging technology. In this paper, we present a QoS brokerbased architecture for web services. The main goal of the architecture is to support the client in selecting web services based on his/her required QoS. To achieve this goal, we propose a two-phase verification technique that is performed by a third party broker. The first phase consists of syntactic and semantic verification of the service interface description including the QoS parameters description. The second phase consists of applying a measurement technique to compute the QoS metrics stated in the service interface and compares their values with the claimed one. This is used to verify the conformity of a web service from the QoS point of view (QoS testing). A methodological approach to generate QoS test cases, as input to QoS verification is used. We have implemented a prototype that includes the verification and certification components of the broker. We performed experiments to evaluate the importance of verification and certification features in the selection process using real web services.