Web Services (WSs) are the most used implementation of service-oriented architectures allowing the construction and the sharing of independent and autonomous software. WS composition consists in combining several WSs into a Composite one, which becomes a value-added service, in order to satisfy complex users queries. Thus, the WS composition process may imply several phases to identify how and which WSs will conform the Composite WS, including specification, verification, evaluation, WSs selection, and execution. As it is known, Petri Nets are the main formal models used to describe static vision of a system and dynamic behavior of processes. Then, Petri Nets are well suited to model internal operations of WSs and interactions among them as well as to model the processes in all phases of the WS composition process. In this article we present a review of approaches using Petri Nets for WS composition. Moreover, we describe our experiences in this field: a transactional-QoS-driven WS selection approach and a framework for reliable execution of Composite WSs based on Colored Petri Nets. © Springer-Verlag 2013.