Service discovery becomes a key to accelerating the evolution of web services as the number of services is expected to increase dramatically. In this paper, we introduce two types of dependency between interfaces in a service to our service matchmaking strategy. Dependency on Assignment defines the dependency between the input and output interfaces of an operation, while Dependency on Sequence defines the invoking order among operations of a service. A formal service specification describing the two types of dependency is given. And based on it, a novel service matchmaking algorithm is introduced, distinguishing different matchmaking strategies for different transmission types of operations. Based on extensive experiments, we show that exploring dependency between interfaces is a promising way to realize intelligent service discovery.