Service Discovery Protocols (SDPs) provide mechanisms that allow networked devices and applications to advertise and locate services with minimum or no human intervention. For fixed networked devices, SDPs such as SLP, Bonjour, and UPnP have been proposed. For more dynamic networked environments such as ad hoc, sensor, and wireless networks, a set of discovery technologies have been designed to operate optimally in such conditions; these include protocols like Ariadne, Allia, GSD, and UDDI. Hence, it is possible to advertise and discover services in diverse network types using one of a suite of technologies. Importantly, there are differences between individual protocols in terms of: (i) service description language, (ii) message format, (iii) directory architecture, (iv) discovery protocol behavior, (v) network communication, and (vi) nonfunctional features. These differences mean it is not possible to discover services with one protocol that is advertised by another and vice versa; we characterize this as service discovery protocol heterogeneity. In this article, we propose SeDiM, a dynamic middleware solution to allow heterogeneous discovery protocols within and across different domains to interoperate with one another. SeDiM is evaluated within a case study that demonstrates transparent interoperation of protocols including SLP and Bonjour in highly heterogeneous environments.