Web Services offer an interoperability model that abstracts from the idiosyncrasies of specific implementations; they were introduced to address the increasing need for seamless interoperability between systems in the Business-to-Business domain. We analyse the require- ments from this domain and show that to fully address interoperability demands we need to make use of semantic descriptions of Web Services. We therefore introduce the Web Service Execution Environment (WSMX), a software system that enables the creation and execution of Semantic Web Services based on the Web Service Modelling Ontology. Providers can use it to register and offer their services and requesters can use it to dynamically discover and invoke relevant services. WSMX allows a requester to discover, mediate and invoke Web Services in order to carry out its tasks, based on services available on the Internet.