The interest surrounding the Web services (WS) composition issue has been growing tremendously. In the near future, it is awaited to prompt a veritable shift in the distributed computing history, by making the Service-Oriented Architecture (SOA) a reality. Yet, the way ahead is still long. A careful investigation of a major part of the solutions proposed so far reveals that they follow a workflow-like compositionapproach and that they view failures as exceptional situations that need not to be a primary concern. In this paper, we claim that obeying these assumptions in the WS realm may constrain critically the chances to achieve a high-dependability level and may hamper significantly flexibility. Motivated with these arguments, we propose a WS composition modeling approach that accepts failures inevitability and enriches the composition with concepts that can add flexibility and dependability but that are not part from the WS architecture pillars, namely, the state, the transactional behavior, the vitality degree, and the failure recovery. In addition, we describe a WS composition in terms of definition rules, composability rules, and ordering rules, and we introduce a graphical and a formal notation to ensure that a WS composition is easily and dynamically adaptable to best suit the requirements of a continuously changing environment. Ourapproach can be seen as a higher level of abstraction of many of the current solutions, since it extends them with the required support to achieve higher flexibility, dependability, and expressiveness power.