Multimedia communications over WLAN is widely acknowledged as one of the key, emerging applications for wireless LANs. As with any multi-service network, there is the need to provision the WLANs with the QoS mechanisms capable of guaranteeing the requirements of various services. The IEEE 802.11e (EDCA) standard defines the required QoS mechanisms into the protocol architecture of IEEE 802.11 WLANs. However, recent studies have shown that EDCA performs poorly when the medium is highly loaded due to the high collision rate. This situation has led many researchers to design techniques aiming to improve the performance of EDCA, such as real-time fast collision resolution (RT-FCR) and adaptive fair EDCF (AFEDCF). However, the main deficiency of many of the proposed mechanisms to date comes from their inability to properly interoperate with legacy IEEE 802.11 (DCF) systems. Moreover, the implementation of many of the proposed QoS mechanisms requires important and incompatible changes to the IEEE 802.11e specifications. In this paper, we introduce a novel IEEE 802.11e-based QoS protocol capable of providing QoS support to multimedia communications, and able to properly interoperate with legacy DCF-based stations. Our design has been based on an in-depth analysis of the several operation modes of both standards. This should ensure full compatibility of operation: an important feature since the transition from the IEEE 802.11 to the IEEE 802.11e will take some time making more likely the existence of hybrid scenarios where both standards will have to coexist. In this work, we carry out a comparative performance evaluation when supporting different services, such as, voice, video, best-effort, background and in the presence of traffic generated by legacy 802.11 (DCF)-based stations. Our simulation results show that the proposed mechanism outperforms the EDCA and other QoS-aware schemes recently reported in the literature. © 2008 Elsevier B.V. All rights reserved.