Conventional multi-rate IEEE 802.11 Wireless LANs (WLANs) are associated with the so-called performance anomaly to describe the phenomenon of high bit rate nodes being dragged down by slower nodes. This anomaly is known to be an impediment to obtaining high cumulative throughputs despite the employment of effective link adaptation mechanisms. To cope with the performance anomaly, air-time fairness has been proposed as an alternative to throughput fairness, the latter being a main characteristic of the IEEE 802.11 Distributed Coordination Function (DCF). In this paper, we propose a novel distributed air-time fair MAC (Medium Access Control) without having to change the operation of the conventional DCF. In the proposed MAC, each node in the system runs multiple instances of the conventional DCF back-off algorithm where the number of DCF instances for the nodes can be chosen in a distributed manner. Both analytical and simulation-based results are provided to validate the effectiveness of the proposed air-time fair MAC.