Abstract Because web services are highly interoperable, they are capable of providing uniform access to underlying technologies, allowing developers to choose between competing services. Workflow languages, such as BPEL, compose and sequence Web service invocations resulting in meaningful, and sometimes, repeated tasks. Their prevalence means there may be multiple Web services that perform the same operation with some better than others depending on the situation. Their potential for being unavailable at critical workflow execution times forces a reliance on such redundant services. One remedy for unavailability and situational awareness constraints is using quality of service factors and user-directed preferences to assign priorities to workflows and services to perform run-time replacement. In this paper we describe a novel approach to self-adapting workflow reconfiguration. We discuss the implementation of our approach embodied by the Next-generation Workflow Toolkit that supports runtime workflow reconfiguration using BPEL with a commercial workflow engine. A key design feature is the decoupling of user-directed changes regarding service priority from the actual workflow execution, allowing NeWT to effectively manage and recover from workflow changes at any time. We evaluate NeWT by comparing the same example across multiple commercial systems that claim reconfiguration capabilities.