We consider the medium access control (MAC) layer for very high-speed Wireless LANs, which is designed to support rich multimedia applications such as highdefinition television. In such networks, the physical (PHY) layer data rate is proposed to exceed 216Mbps. The legacy MAC layer, however, greatly restricts the performance improvement due to its overhead. It has been shown that MAC utilizes less than 20% of the transportation ability provided by the PHY layer. To mitigate this inefficiency, we propose an Aggregation with Fragment Retransmission (AFR) scheme, which supports transmissions of very large frames and partial retransmissions in the case of errors. Aggregation allows for increased performance despite pertransmission overhead while partial retransmission alleviates the risk of losing the entire frame. Extensive simulations show that AFR fundamentally outperforms the legacy MAC protocol. It is particularly effective for applications with high data rates and large packet sizes such as HDTV and high-rate UDP traffic. For applications with very low data rates and small packet sizes such as Voice over IP, AFR performs slightly better.