We report a new fullerenelike material consisting of cross-linked nano-onions of C and N. Growth of the onion shells takes place atom by atom on a substrate surface and yields thin solid films during magnetron sputter deposition. Electron microscopy and energy loss spectroscopy show that the core shell contains up to 20 at. % N corresponding to C(48)N(12) aza-fullerene composition. Nanoindentation of this nanostructured material gives high resilience with hardness 7 GPa, Young's modulus 37 GPa, and complete elastic recovery after loading with 0.5 mN to a depth of 75 nm. Total energy calculations show the stability of C(60-2n)N(2n) aza-fullerenes and suggest the existence of a novel C(48)N(12) molecule.