Service discovery is the process of locating suitable services and retrieve their descriptions in response to the user requirements. The discovery process should include functional, behavioral and executional semantics of the services towards dynamic integration with user’s applications. However, most of the discovery approaches exist in the literature primarily relies only on functional aspects and data formats of the services. To address these issues, this paper proposes an interface driven service discovery mechanism. For this purpose, a conceptual model of service interfaces is proposed to express the related functional and behavioral facets based on which services are discovered. Further, a service interface behavioral model called, Colored Petri Net for Service Interface (CPSI), is also proposed to represent the conceptual constructs of service interfaces and behavioral aspects of related services. It also implements a two staged service discovery algorithm to find the target service and to integrate with the interface dynamically. The proposed CPSI and service discovery algorithm is simulated using the CPN tool. Further, the expressiveness of the proposed mechanism is illustrated using a suitable case study.