Eight stratigraphic sections from well-exposed outcrops of the Early to Middle Miocene Tanjong Formation in the Kalabakan area, southeast Sabah, were investigated using an integrated approach, in which a comprehensive sedimentological facies analysis was linked with bulk geochemistry and palynological analyses. The integration of facies analysis, elemental CHNS, Fourier-transform infrared spectroscopy (FTIR), and palynological data provided a refined evaluation of the origin of organic matter (OM) and the reconstruction of the paleodepositional model. Seven facies associations were classified in the studied Tanjong Formation from 12 lithofacies components, interpreted as environments ranging from fluvial-deltaic to shallow marine: FA1—Floodplain, FA2—Fluvial channel, FA3—Coastal peat mires, FA4—Tidal flat, FA5—Delta front, FA6—Mouth bar, and FA7—Upper shoreface. Evaluation of the C/N ratio ranged between 4 and 48, and the total sulfur content ranged from 0.5 to 3. Elemental CHNS analysis suggests that the organic matter extracted from the coal and mudstone originated from terrestrial plants and fresh marine plankton. Accordingly, the three most prevalent FTIR spectra from the coal and mudstone samples were the OH- functional group stretching, the absorption spectrum of aromatic C=C stretching, and aromatic in-plane/out-of-plane C-H bending. Terrestrially derived organic matter within the examined samples was further validated by the predominance of aromatic compounds, and the palynological analysis indicated a back-mangrove freshwater pollen assemblage and a lower coastal plain setting proximal to the marine environment. The integrated findings from this research are vital in reconstructing a paleodepositional environment model that will improve the predictability of the petroleum system mechanisms and the future hydrocarbon potential for conventional petroleum exploration.