In this paper we studied the combination of advanced oxidation processes (AOPs), i.e., TiO-based photocatalysis and photo-Fenton process, on the degradation of aqueous solutions containing a low (90 ppm) concentration of formaldehyde. Heterogeneous nanostructured catalysts, supported on polymeric nanofibers, were used; for comparison, some homogeneous or partly heterogeneous systems were also analyzed. Furthermore, to make the process more sustainable (in terms of costs and safety) no hydrogen peroxide was added to the system. The results showed that the combination of AOPs gave a synergy since the presence of iron was beneficial in promoting the photocatalytic activity of TiO while TiO was beneficial in promoting the photo-Fenton reaction. Moreover, very good results were obtained using fully heterogeneous nanostructured catalysts (based on TiO and FeSO), without the need to add HO.