The cyanate anion (NCO-) is a species of considerable astrophysical relevance. It is widely believed to be embedded in interstellar ices present in young stellar objects but has not yet been detected in the dense gas of the interstellar medium. Here we report highly accurate laboratory measurements of the rotational spectrum of the N13CO- isotopologue at submillimeter wavelengths along with the detection of three additional lines of the parent isotopologue up to 437.4 GHz. With this new data, the rotational spectrum of both isotopologues can be predicted to better 0.25 km s-1 in equivalent radial velocity up to 1 THz, more than adequate for an astronomical search in any source. Moreover, a semiexperimental equilibrium structure of the anion is derived by combining the experimental ground-state rotational constants of the two isotopologues with theoretical vibrational corrections, obtained by using the coupled-cluster method with inclusion of single and double excitations and perturbative inclusion of triple excitations (CCSD(T)). The estimated accuracy of the two bond distances is on the order of 5 × 10-4 Å: a comparison to the values obtained by geometry optimization with the CCSD(T) method and the use of a composite scheme, including additivity and basis-set extrapolation techniques, reveals that this theoretical procedure is very accurate.