Service Composition is one of the most important features offered by Service Oriented Computing. The composition allows a new service to be created through the reuse of existing ones. The process of creating a composition involves discovering the necessary services and combining them in an appropriate manner using specific languages and tools. This process, however, is still carried out mainly by hand. Considering the dynamic nature of distributed services, manual composition may become too complex, affecting the productivity gains provided by reuse. Proposals to fully or partially automate this process already exist, most of them based on Automated Planning algorithms borrowed from Artificial Intelligence. Although functional, these approaches have practical problems that hinder their effective implementation in production scenarios. In this Thesis, we addressed some of the practical problems of automated composition, starting with the need for formal descriptions of services. These formal descriptions are necessary for the composition algorithms, however, are rarely available from services. This issue was addressed by means of reverse engineering a repository of service compositions. By analyzing how the services were related to each other in the compositions, it was possible to obtain the necessary information for the algorithms to work. We also evaluated the quality of the compositions generated by the algorithms and their similarity with respect to compositions created manually. Automated Planning algorithms from the literature have been modified in order to generate solutions closer to those expected by the developer. Finally, the composition algorithms were adapted to accept incomplete specifications, thus allowing the developer to obtain a solution even not knowing a priori all the composition details. Comparisons with automated planning tools were conducted in order to ascertain the effectiveness of the algorithms. The results show that the automated composition, as presented in the Thesis, can be an invaluable tool to the service developer.