When digital multimedia data are retrieved from distributed digital archives, Quality of Service (QoS) criteria can be used to enhance the user's usability. In this paper, assuming best-effort networks as the infrastructure, we describe a multimedia (MM) retrieval method based on the QoS concept for MM data archives in heterogeneous communication environments. We introduce a multi-level QoS model and use response time, which is calculated based on a system-level QoS criterion, as an application-level QoS criterion. The order of retrieving MM data is determined, based on both key-word matching using key words specified by the user and the application-level QoS criterion. A prototype system is developed for retrieving sightseeing-related MM data including video, images, voice, and text. The proposed method of data retrieval has a shorter response time than methods that do not take QoS criteria into account. Also, a search method based on key-word association is described that enables wide-area search and effective information finding. (C) 2002 Elsevier Science Ltd. All rights reserved.