The rapid evolution of the Internet and its business tools is enabling the transformation and deployment of business processes as highly modular e-services that can be flexibly and dynamically composed to form ad-hoc workflow. This research prepares for the proliferation of automated, Internet-based workflow, by contributing a suite of protocols for self-organizing brokering communities that enables the discovery of relevant e-services. We present protocols and architecture for e-service brokering communities, and discuss their use in workbase, an Internet-based, automated workflow system over e-services. The brokering protocols are based on a three-tier architecture of agents, brokers and superbrokers. We also present an infrastructure for dynamically composing new services from exiting e-services on the Internet. An implementation using JKQML of brokering communities is provided along with the architecture and design of our e-services and workflow concepts. © 2001 IEEE.