Current Web technologies provide the basis for publishing and composing large number of Web Services which are characterized by functional, non-functional, and transactional properties. Although the research community has proposed several approaches to efficiently solve problems as service selection and composition, some of these solutions may be incomplete, i.e., they may fail producing a solution when solutions exist. In this paper we propose a non-chronological backtracking strategy which is implemented in a state-of-the-art composition algorithm named PT-SAM, and completeness is achieved in the context of transactional web service composition. Empirical results suggest that the proposed approach may overcome the chronological backtracking strategy by up one order of magnitude. © 2012 Published by Elsevier Ltd.