The spectrum of deployed wireless cellular communication systems is found to be under-utilized, even though licensed spectrum is at a premium. To efficiently utilize the bandwidth left unused in a cellular system, which we denote as the primary system (PRI), we design a system with an ad hoc overlay network, which we denote as the secondary system (SEC). The basic design principle is that the SEC operates in a nonintrusive manner and does not interact with the PRI. We develop the AS-MAC, an Ad hoc SEC Medium Access Control protocol to enable the interoperation of the PRI-SEC system. We address a number of technical challenges pertinent to this networking environment, and evaluate AS-MAC. Our performance evaluation results show that, in a single-hop ASN, the AS-MAC transparently utilizes 75% of the bandwidth left unused by the PRI, while, in multi-hop ASNs, due to spatial reuse, the AS-MAC can utilize up to 180% of the idle PRI resources.