Because petroleum-related natural organic matter (NOM), such as humic substances, is extremely heterogeneous and complex, characterizing and identifying its chemical structure at the molecular level is attracting considerable attention. Among the different techniques for mass analysis, ultrahigh-resolution mass spectrometry methods, such as FT-ICR MS and its coupling with other complementary methods, have proven to be crucial for structurally characterizing complex environmental mixtures owing to their excellent analytical power. In particular, their ultrahigh resolution, unrivaled mass accuracy, remarkable ionization specificity, excellent ion activation, and high degree of flexibility for combination with hybrid instruments offer a reliable platform for analyzing petroleum-NOM molecules. This account, aimed at contributing to the advancement of petroleum-NOM molecule analysis, summarizes the application of FT-ICR MS with different ionization sources and its coupling with other complementary methods developed by our research group.