For the first time, the development of prediction models of the penetration grade and the softening point of vacuum residues (VRs) and pavement asphalts, from the structural data obtained with proton nuclear magnetic resonance (1H NMR) and relaxometry data obtained via low-field nuclear magnetic resonance (LF NMR), is reported. The correlation between the structural data (1H NMR, percentage of different proton kinds), the relaxometry data (T2, spin–spin relaxation time), and the properties, was measured with principal component regression (PCR). The best models were those obtained with PCR, which were validated via k-fold cross-validation, with k = 10. In particular for the VR, the best model for the penetration grade was obtained from LF NMR, with a training R2 of 0.99 and a validation R2 of 0.96; the best softening point was obtained from the combination of 1H NMR and LF NMR, with R2 values of 0.99 and 0.87, respectively. For the asphalts, the best model for the penetration grade was also obtained from the combination of 1H NMR and LF NMR, with R2 values of 0.99 and 0.94, respectively. Note that these prediction methods require less sample quantity, time, and personal effort than the ASTM standards.