Vehicular Ad hoc Networks (VANETs) should provide the vehicles with reliable safety message broadcasts and efficient non-safety message transmissions. The IEEE 1609.4 MAC is designed for VANETs to support multi-channel operations, but the safety message broadcast is not much reliable and the Service Channel (SCH) resources are not fully utilized. In this paper, we propose a new multi-channel MAC for VANETs, named HER-MAC, which supports both TDMA and CSMA multiple access schemes. The HER-MAC allows vehicle nodes to send safety messages without collision on the Control Channel (CCH) within their reserved time slots and to utilize the SCH resources during the control channel interval (CCHI) for the non-safety message transmissions. Compared to the current IEEE 1609.4, the proposed HER-MAC protocol is more reliable in the safety message broadcast, efficient in the service channel utilization.