Service composition refers to the process of developing the complex services from existing services. In order to add or remove functionalities of the composite services and to reduce the human intervention, the service composition process should be dynamic, scalable, and reusable. For the purpose, this paper proposes a Colored PetriNet based approach for service composition. In the proposed mechanism, firstly, a conceptual model of service interface has been devised. Based on the conceptual model a Colored PetriNet (CPN) based model, called Colored PetriNet for Service Composition (CPSC) has been proposed to represent the behavioral aspects of the conceptual constructs of service interfaces and different composition aspects of the constituent services. It also implements a service composition algorithm to execute the composition sequence of services. Moreover, the proposed CPSC along with the algorithm are illustrated with a suitable case study and simulated using CPN tool. The result shows that the proposed algorithm can successfully compose services based on the user requirements. Beside these, the state space report of the proposed CPSC validates the standard behavioral properties of the concerned system.