Novel structures of oxa- and thia-fullerenes at various oxidation states have been computed systematically for the first time. At the B3LYP/6-31G* density functional level of theory, the most stable C59O, C59O4 and C59S4- represent cage opened structures with an eight-membered-ring orifice, bearing C=O or C=S moieties and two fused five-membered rings. On the other hand, C59S, C59S2+ and C59O2+ are cage closed fullerenes. The calculated nucleus independent chemical shifts (NICS) of all these compounds are presented.