NATO has identified web services standards as a key enabler for interoperability between the different military systems used by various NATO nations. Compared to many civilian systems, mil- itary networks vary greatly in terms of comput- ing resources, network bandwidth, mobility and stability, and distributed applications use several different networks concurrently or interact across them. In such dynamic and heterogeneous environments, runtime service discovery is a necessity. According to the W3C, “discovery is the act of locating a machine-processable description of a Web service-related resource that may have been previously unknown and that meets certain functional criteria.” In this article we present our approach to service discovery, where we combine web services standards and proprietary solutions using our prototype inter- operability gateway. This approach has been experimentally evaluated in a military experi- ment featuring both mobile ad hoc networks and fixed infrastructure networks, and the results show that transparent discovery between propri- etary solutions and web services discovery stan- dards can be achieved.