The spectrum of deployed wireless cellular communication systems is found to be underutilized, even though licensed spectrum is at a premium. To efficiently utilize the bandwidth left unused in a cellular system, the primary system (PRI), we propose an overlaid ad hoc secondary network (ASN) architecture, with the ASN operating over the resources left unutilized by the PRI. Our basic design principle is that the ASNoperates in a nonintrusive manner and does not interact with the PRI. In this article we present the ad hoc secondary medium access control (AS-MAC) protocol to enable PRI-SEC interoperation, address a number of technical challenges pertinent to this networking environment, and evaluate the performance of the AS-MAC. In a single-hop ASN the AS-MAC transparently utilizes 75 percent of the bandwidth left unused by the PRI, while in multihop ASNs, due to spatial reuse, the AS-MAC can utilize up to 132 percent of the idle PRI resources in our experiments.