This article discusses technical issues related to delivery of multimedia services, such as video-on-demand, over heterogeneous networking environments. In particular, it describes the design and implementation of an experimental system for multimedia service interworking between a DAVIC (Digital Audio Visual Council) domain and an Internet domain. The system, called MIDDLEMEN (middlemen for multimedia environment), consists of the broker and the interworking unit, which work together to provide multimedia services across different types of networks in a seamless manner. The broker acts as a guide to multimedia services, and complements servers or clients that are not equipped with full functionality. The broker also controls the resources in MIDDLEMEN. The interworking unit performs various translation functions under the control of the broker, including stream transport protocol conversion, traffic monitoring and bit-rate control, service gateway conversion, and stream control conversion. Current implementation supports the delivery of a DAVIC-compliant VOD service from an ATM network to an IP network