Cognitive Radio (CR) can effectively reuse the same frequency of the existing legacy systems with the help of the adaptivity provided by the software defined radio technique and the intelligence learned by sensing the huge spectrum in the surrounding environment. One fundamental issue for a CR network is how CR users establish an overlaying ad hoc link on licensed and unlicensed bands. On licensed band, the CR user has to detect the presence of the primary user and vacate accordingly to avoid the interference. On the unlicensed band, the medium access shall support the quality of service (QoS) as well as improving the efficiency and fairness for the spectrum usage. In this paper, by moderately reshaping the legacy carrier sense multiple access (CSMA) medium access control (MAC) protocol, we propose a cognitive and distributive MAC protocol to establish a CR ad hoc network with QoS provisioning, high efficiency and fairness. Through the simulations by NS-2, the proposed cognitive MAC protocol can improve throughput by 50% compared to the legacy carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol, while keeping the dropping rate less than 2% for delay-sensitive applications.