Advances in mobile device technology enable a rich set of distributed capabilities that can be shared among users by encapsulating them in the form of services. These services can be combined to provide enhanced functionality in what is known as service composition. When applied to mobile environments, service composition may face disruptions due to the mobility of both requesters and service providers. Therefore avoiding disruptions by predicting the movements of devices engaged in the service composition is of utter importance. In this paper, we propose a dependable service composition algorithm based on movement prediction that leverages mobility characteristics to estimate the dependability of devices. By using the estimation of contact time of each service provider, we can determine how dependable a service composition path is. Our evaluation results show that proactive estimation service composition dependability can detect service disruptions effectively when compared to other existing approaches.