This paper describes the design and implementation of an experimental system for multimedia service interworking over heterogeneous network environment. The system, called MIDDLEMEN (MIDDLEmen for Multimedia ENvironment), consists of the interworking unit and the service broker, which cooperate to provide seamless multimedia service across different types of networks. The broker subsystem acts as a guide to multimedia services spanning possibly many networks. The interworking subsystem performs various interworking or translation functions under the control of the broker subsystem. In this paper, we mainly discuss the design of the interworking unit of the MIDDLEMEN. For real-time delivery of multimedia services across different networks, the interworking unit performs various functions, including protocol conversion, traffic monitoring and bit-rate control, service gateway conversion, and stream control conversion. Current implementation supports delivery of DAVIC-compliant VOD services to the Internet. We discuss various interworking issues, mainly at service level.