Existing Web Service architectures provide the basis for publishing applications as Web Services (WSs), and for composing existing WSs to provide new functionalities. To fully meet user requests when WSs are composed, functional characteristics of the WSs as well as Quality of Service (QoS) parameters and transactional capabilities of their executions, need to be simultaneously considered. QoS parameters describe WSs in terms of their behavior; transactional capabilities state whether a service is reliable during execution time if unpredictable failures occur. We formalize this WS composition problem as an optimization problem that considers at the same time functional, QoS, and transactional requirements. We also define a utility function that combines functionality, QoS, and transactional WS properties, to guide the service compositor into the space of compositions that best meet the QoS and transactional criteria. In addition, we propose a service compositor, named PT-SAM-Transac, which adapts a Petri-Net unfolding algorithm and efficiently traverses the space of optimal compositions. Our experiments show that PT-SAM-Transac outperforms a state-of-the-art solution (called SAM) by identifying compositions that better meet the QoS and transactional criteria, while the composition time of both approaches are in the same order of magnitude. © 2012 Springer-Verlag.