Service composition is a powerful tool to create new services rapidly by reusing existing ones. Previous research mainly focuses on the wired infrastructure-based environment. With the developments in mobile devices and wireless communication technology in recent years, mobile ad hoc network has received an increasing attention as a new communication paradigm. However, the existing service composition techniques do not work any longer in an ad hoc environment. In this paper, we present the service composition problem in wireless ad hoc network with full consideration of the characteristics of an ad hoc environment. To solve this problem, we develop two service composition routing algorithms, Simple Broadcasting Service Composition and Behavior Evolution Service Composition. The main contribution of our algorithms is that the whole process of service composition is done by the cooperation of nodes on-the-fly instead of a centralized broker to meet the peculiarity of ad hoc networks. Finally, we describe an initial implementation architecture for service composition in wireless ad hoc networks.