The IEEE 1609.4 [1] is a MAC extension of IEEE 802.11p [2] to support multi-channel operations. However, the IEEE 1609.4 does not allow nodes to exchange non-safety messages during the CCH interval. This paper proposes a Vehicular Enhanced Multi-channel MAC protocol (VEMMAC) for Vehicular Ad hoc Networks (VANETs). The VEMMAC adopts the IEEE 1609.4 with alternating sequences of the Control Channel (CCH) interval and the Service Channel (SCH) interval. Different from the IEEE 1609.4, the VEMMAC allows nodes to transmit non-safety messages during CCH interval and broadcast safety messages twice with each in the CCH and SCH interval. Our proposal can utilize the channel resources more efficiently than the IEEE 1609.4. The simulation results show that the proposed VEMMAC protocol achieves higher throughput for service data and is more reliable for safety messages broadcast than other protocols.