Techniques are described for assisting users in dynamically creating and using composite services that are based on other constituent services. In some situations, each constituent service is a Web service (“WS”), and each composite service is a new WS whose execution involves dynamically invoking multiple specified constituent WSes in a specified manner. Such techniques may be used, for example, in conjunction with an electronic WS marketplace via which third-party WS providers make their WSes available to third-party WS consumers who locate and purchase access to those WSes, such as to allow a user to dynamically create a new composite WS that is based on one or more WSes available from other WS providers and that reflects any constraints of the WS marketplace, with the composite WS available for use by other WS consumers. This abstract is not intended for use in interpreting or limiting the scope of the claims.