Microwave and millimeter wave transitions of the CO-N-2 complex were investigated using three different instruments, namely, a pulsed molecular beam Fourier transform microwave spectrometer in the frequency region from 4 to 26 GHz, a microwave-millimeter wave double resonance spectrometer in the frequency regions from 8 to 18 GHz for the microwave and 107-118 GHz for the millimeter wave range, and an OROTRON spectrometer in the frequency range from 107 to 132 GHz. Both a- and b-type transitions associated with the ground-state K = 0 levels and the lower K = 1 levels of the ortho-N-2 states, and with rotational quantum number J up to 19, were measured and analyzed. Nuclear quadrupole hyperfine splittings due to the presence of two equivalent N-14 nuclei were resolved and analyzed to give additional information about the angular anisotropy of the interaction potential. The nuclear quadrupole coupling constants obtained are chi(aa) = 0.196 41(52) MHz for K = 0 levels, and chi(aa) = -1.0391(17) MHz, chi(bb) = 0.0633(17) MHz for the lower K = 1 levels, respectively. The drastic difference between these two sets of coupling constants suggests that the orientation and motion of the N-2 subunit are very different in these two states, and that the complex cannot be adequately described by a semirigid rotor model. In addition, measurements of the rotational spectra of the two new isotopomers containing (CO)-C-13-O-16 and (CO)-C-13-O-18 subunits provide further important information about the CO-N-2 interaction potential.