A Service-Based Application (SBA) is built by defining a workflow that composes and coordinates different Web services available via the Internet. In the context of on-demand SBA execution, suitable services are selected and integrated at runtime to meet different non-functional requirements (such as price and execution time). In such dynamic and distributed environment, an important issue is to guarantee the end-to-end Quality of Service (QoS). As a consequence, SBA provider is required to monitor each running SBA instance, analyze its runtime execution states, then identify proper adaptation plans if necessary, and finally apply the relative countermeasures. One of the main challenges is to accurately trigger the adaptation process as early as possible. In this paper, we present a two-phase decision approach that can accurately analyze the adaptation needs for on-demand SBA execution model. Our approach is based on the online prediction techniques: an adaptation decision is determined by predicting an upcoming end-to-end QoS degradation through two-phase evaluations. Firstly, the end-to-end QoS is estimated at runtime based on monitoring techniques; if a QoS degradation is tent to happen, in the second phase, both static and adaptive strategies are introduced to assess whether it is the best timing to draw the final adaptation decision. Our approach is evaluated and validated by a series of realistic simulations.