Comets provide a unique window into the history of the Solar System as they carry some of the best-preserved material and make it available to in situ exploration. A milestone in comet studies was the European Space Agency’s Rosetta mission, which, for the first time, rendezvoused with a comet, namely 67P/Churyumov-Gerasimenko (67P), and studied it from a close range for two years. Amongst other unexpected insights, data from this mission show that comets contain a surprisingly large portion of organics, both in the refractory and the icy phases. For this work, we evaluated high-resolution mass spectra collected in comet 67P’s inner coma by Rosetta’s ROSINA-Double Focusing Mass Spectrometer (DFMS). In unprecedented detail, we investigated the N- and NO-bearing cometary complex organic molecules (COMs) of the general sum formula CnHmN and CnHmNO, where n and m are the stoichiometric coefficients of carbon and hydrogen. Our discussion-driven approach combines the empirical concept of Occam’s razor with knowledge from studies of relevant astrophysical environments and constraints expected from naive bottom-up assembly of molecules. We present an exemplary minimal and non-unique set of molecules needed to explain the DFMS observations. While this set might not capture the full organic diversity, but rather its lower limit, it identifies many N- and NO-bearing COMs with reasonable certainty, while excluding others, potentially informing future observational campaigns, and hence contributes to the exploration of the origin and evolution of organic complexity in space. Among the key results is strong evidence for an abundant presence of heterocycles as well as substantial alkylation of both cyclic and acyclic species. These findings align well with reports on soluble organic matter in meteorites and asteroids and underpin once more the potential importance of such extraterrestrial organic material as a feedstock for terrestrial prebiotic chemistry.