We report electronic structure calculations using density-functional theory (local density approximation (LDA) and generalized gradient approximation (GGA); plane waves and muffin-tin orbitals; pseudopotentials and all-electron approaches) on nonstoichiometric CoNxO1-x oxynitride phases. The preference of the experimentally suggested zinc-blende structure type over the rock-salt type is confirmed and explained, on the basis of COHP (crystal orbital Hamilton population) chemical bonding analyses, by reduced Co-Co antibonding interactions in the ZnS structural alternative. A pressure-induced phase transition into the NaCl type, however, is predicted at approximately 30 GPa. Supercell calculations touching upon the exact composition and local structure of CoNxO1-x provide evidence for a broad range of energetically metastable compositions with respect to the zinc-blende-type boundary phases CoN and CoO, especially for the more oxygen-rich phases. All non-stoichiometric compounds are predicted to be metallic materials which do not exhibit significant magnetic moments. Likewise, there is no indication for anionic ordering such that random anion arrangements are preferred.