Service composition is a process by which the services offered by devices may be combined to produce new, more complex services. In a pervasive computing environment where many devices exist and offer services, it is particularly desirable to fully automate this composition so end users do not need to be technically sophisticated. Earlier work done by Pourreza introduced a system to do fully automated service composition and to rank the services so produced by order of expected usefulness to the end user(s). My thesis research extends the work done by Pourreza in two ways. First, and most importantly, it adds support for services that have associated Quality of Service (QoS) characteristics. This allows me to ensure that I only generate composite services that are compatible in terms of the provided and required QoS characteristics of their component services. Further, it allows me to rank the generated composite services based on how well they meet the desired QoS preferences of users. Second, I extend Pourreza’s work by adding support for compositions involving services from outside a persistent computing environment (e.g. those provided via available Internet or 3G network access). I have built a prototype for the system to illustrate feasibility and to assess the overhead of supporting QoS in composition. I have also developed a regression model (based on collected user input regarding QoS preferences for services) that can be used to effectively rank compositions based on QoS for a variety of persistent environments. My results show that my approach is both feasible and effective.