Much effort is being made by the IT industry towards the establishment of a Web services infrastructure and the refinement of its component technologies to enable the sharing of heterogeneous application resources. Traditional roles of the service provider, service requestor and service broker and their interactions are now being improved upon to enable more effective services.The implementation of the Web Service broker is currently limited to being an interface to the service repository for service registration, browsing and/or programmatic access. In this work, we have extended the functionality of the Web services broker to include constraint specification and processing, which enables the broker to find a good match between a service provider's capabilities and a service requestor's requirements. This paper presents the extension made to the Web Services Description Language to include constraint specifications in service descriptions and requests, the architecture of a Constraint-based Broker, the constraint matching technique, some implementation details, and preliminary evaluation results.