High quality paper samples have been oxidized with a specific oxidant to reproduce one of the possible causes of the aging of paper. All samples have been characterized by 13C CP-MAS NMR spectroscopy. The artificial aging of paper has been monitored using a standard NMR relaxometer and the results have been compared with the corresponding data obtained using an unilateral NMR relaxometer. Experimental values obtained with both techniques are in agreement, demonstrating that unilateral NMR relaxometric measurements constitute a suitable non-invasive method for assessing the degradation process of cellulose-based materials. The sensitivity of the non-invasive NMR method allows the detection of degradation even at a very early stage. Effects due to the sample volume and to the penetration depth have been investigated.