In this paper, we consider an ad hoc network overlaying a legacy time-division multiple access (TDMA) system. This kind of ad hoc and infrastructure-based coexisting architecture can have an important application for the future cognitive radio (CR) network. To establish an overlaying ad hoc network in the presence of primary users, the medium access control (MAC) protocol shall achieve high spectrum utilization, avoid interfering the primary user and establish the link quickly. To this end, we propose four enhanced mechanisms for the carrier sense multiple access with collision avoidance (CSMA/CA) MAC protocol: (1) a neighbor list establishment mechanism for recognizing spectrum usage opportunities, (2) a set of contention resolution methods to reduce the collision and delay variance, (3) an invited reservation procedure for meeting the delay requirements of real-time traffic, and (4) a distributed frame synchronization mechanism for coordinating transmission without a centralized controller. Compared to the legacy IEEE 802.11 MAC protocol, the proposed CSMA/CA MAC protocol enhancement can improve the system throughput by 50% through analysis and NS-2 simulations, while keeping the dropping rate lower than 2% for delay-sensitive traffic. Furthermore, the standard deviation of the access delay is reduced by five times. With these QoS enhanced mechanisms, the proposed cognitive CSMA/CA MAC protocol can allow an ad hoc network to coexist with the legacy TDMA system.