With an increasing number of services developed and offered in an enterprise setting or the Web, users can hardly verify their requirements manually in order to find appropriate services. In this thesis, we develop a method to discover semantically described services. We exploit comprehensive service and request descriptions such that a wide variety of use cases can be supported. In our discovery method, we compute the matchmaking decision by employing an efficient model checking technique.