Methods and apparatus are provided for specifying Web service interfaces and for processing Web service messages using protocol multiplexing. A Web service comprised of a plurality of sub-services (or clients of the Web service) are designed in accordance with the present invention by analyzing a plurality of micro-protocols between two or more of the sub-services, the Web service, and one or more clients of the Web service. A composite message is created if a plurality of messages of the micro-protocols have the same sender and receiver and belong to compatible message sequences. The present invention ensures that the execution of two or more message handlers is based on a defined execution order, when one or more collaborations of the micro-protocols are dependent on other collaborations. A Web service according to the present invention decomposes one or more incoming messages into a plurality of micro-messages (or composes one or more outgoing messages from a plurality of micro-messages) and provides a plurality of message handlers that process (or generate) said plurality of micro-messages.