Prevalent approaches for automatically composing Web services (WSs) into Web processes predominantly utilize planning techniques to achieve the composition. However, many of the planning methods do not scale efficiently to large processes. In addition, they lack the capability to operate directly on the WS descriptions, and specifically on the preconditions and effects which may be represented using first order logic based languages. Instead, many of these methods ground and propositionalize the higher level logic resulting in exponentially many more states. In this paper, we present a new framework for composing Web services into processes, called Haley, that exploits the natural hierarchy often found in Web processes. Haley uses symbolic techniques that operate directly on first order logic based representations of the state space to obtain the compositions. In addition to providing an approach that handles the uncertainty inherent in Web services, Haley guarantees cost-based optimality and offers an approach potentially scalable to large real world processes.