The spectrum of deployed wireless cellular communication systems is found to be under-utilized, even though licensed spectrum is at a premium. In this paper, we design a system with an ad hoc overlay network, which we denote as the secondary system (SEC), to efficiently utilize the bandwidth left unused in a cellular system, which we denote as the primary system (PRI). The basic design principle is that the SEC operates in a non-intrusive 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 investigate a number of AS-MAC variants. Our performance evaluation results indicate that AS-MAC can transparently utilize up to 80% bandwidth left unused by the PRI.