The dynamic nature of the Internet poses various challenges to the successful execution of composite Web services. Failures are samples of these challenges. It needs to be addressed for the smooth progress of Web service composition. Unfortunately, the de facto standard for modeling composition namely BPEL is not equipped with mechanisms that let Web services "heal" themselves in case of failures. In addition, current BPEL engines lack appropriate facilities that permit satisfying self-healing requirements like handling in a transparent way functional failures of component Web services during runtime. This paper presents an approach for enhancing BPEL engines with such facilities. This enhancement happens through the following steps: identify possible categories of failures, develop solutions to automatically recover from these failures, and suggest architectural extensions to BPEL engines (with focus on ActiveBPEL) to support these solutions. We also present a proof-of-concept prototype that illustrates our ideas. © 2008 IEEE.