In this paper we introduce a novel Network Coding-based Medium Access Control (MAC) protocol for Vehicular Ad-Hoc Networks (VANETs) that use cooperative Automatic Repeat reQuest (ARQ) techniques. Our protocol co-ordinates the channel access among a set of relays that are capable of using network coding in order to minimize the number of the total transmissions, thus enhancing the performance of the network in terms of Quality of Service (QoS) metrics. The proposed solution is compared to other cooperative schemes, while analytical and simulation results are provided to evaluate our protocol.