Hydrogen depleted environments are considered an essential requirement for the formation of fullerenes. The recent detection of C60 and C70 fullerenes in what was interpreted as the hydrogen-poor inner region of a post-final helium shell flash planetary nebula (PN) seemed to confirm this picture. Here, we present strong evidence that challenges the current paradigm regarding fullerene formation, showing that it can take place in circumstellar environments containing hydrogen. We report the simultaneous detection of polycyclic aromatic hydrocarbons (PAHs) and fullerenes toward C-rich and H-containing PNe belonging to environments with very different chemical histories such as our own Galaxy and the Small Magellanic Cloud. We suggest that PAHs and fullerenes may be formed by the photochemical processing of hydrogenated amorphous carbon. These observations suggest that modifications may be needed to our current understanding of the chemistry of large organic molecules as well as the chemical processing in space.