This paper discusses a layered workflow software architecture for distributed coordination of workflows over web services and proposes fundamental enhancements to the web services infrastructure that facilitate the layered workflow software architecture. We verify our layered approach using a detailed simulation and a proof-of-concept prototype implementation. Our proposed architecture for Web Service Coordination Management Middleware (WSCMM) is a simple but powerful enhancement to the web service infrastructure enabling the services to locally manage their dependencies and to handle messages resulting from multiple workflows. We have carried out a detailed simulation to identify key components of our middleware architecture. We also compare and contrast our architecture with the current web service technologies. Our experiments demonstrate that we can develop both centralized and distributed workflows over the architecturally enhanced web services with relative simplicity. In addition, our lightweight coordination components with footprint no larger than 150 KB allow these workflows to be executed even on a handheld.