Petroleum asphaltenes are a complex mixture of organic molecules containing mainly fused polyaromatic and naphthenic systems and pendant chains, polar moieties with heteroatoms (S, N, and O), and transition metals. A variety of spectroscopic techniques has been employed to characterize asphaltenes, but their structures remain largely elusive because of the complexity, variety of samples, and assignment limitations. Carbon-13 nuclear magnetic resonance (13C NMR) spectroscopy has contributed extensively to asphaltene characterization. However, proper assignment of 13C NMR spectra is very challenging because spectra of natural asphaltenes feature a large number of peaks in unusual environments, which may be hard to assign and interpret. We employ the dispersion-corrected ωB97X-D density functional with 6-31G(d,p) basis set to rationalize common trends in the 13C NMR chemical shifts of asphaltene model compounds. The calculated 13C NMR chemical shifts for a calibration series of 14 aromatic and heterocyclic reference compounds containing C atoms of types similar to those in the asphaltene model compounds are found to correlate linearly with the respective experimental values. The linear fitting yields a correlation coefficient of R2 = 0.99 and absolute errors of less than 10 ppm. Moreover, we calculate and calibrate the 13C chemical shifts of asphaltenes extracted from Brazilian vacuum residues to analyze and correlate the C atom types with those of the reference compounds. It is found that the presence of heteroatoms as well as environments with a high aromatic condensation index can significantly affect the chemical shifts. The effect of heteroatoms on the chemical shift, a situation that has scarcely been addressed in the literature, is evaluated here in detail. The results are intended to help interpret 13C NMR spectra and allow for a more complete characterization of asphaltene molecules.