Display omitted •Multi-way analysis classifies crude oil samples by their origin.•DOSY NMR spectra are good experimental data for predicting crude oil stability.•Machine learning enables accurate predictive stability models.•Robust approach shows a great potential for practical applications. Crude oils are extremely complex organic mixtures, composed of various constituents ranging in size, shape and polarity. Obtaining a detailed insight into the petroleum composition is of highest priority for quality evaluation of crude oils and crude oil product performances. The stability of crude oils and their components represents one of the major challenges in petroleum industry, since there is no existing single method to determine the stability of all fractions. In this study, statistical multi-way analysis (MWA) and machine learning (ML) methods were coupled with diffusion-ordered NMR spectroscopy (DOSY) and compared to different crude oil stability affecting parameters in order to explore possibilities to predict crude oil stability. The potential of this approach was explored to identify and classify the crude oils of different origin according to their composition, stability, density and diffusion properties. With the application of MWA using the TUCKER3 decomposition model for a set of DOSY NMR spectra, the principal components were determined for the model (5,5,5), which described 99.89 % of the total variance. The reduced space of the first 3 principal components was used for the sample classification. Similar samples were identified, and reduced space was further utilized for the regression of measured stabilities. Extensive ML multivariate linear regression was carried out for modeling crude oil stability in relation to DOSY NMR spectra and other measured properties, such as aromaticity, API gravity, percentage of aliphatic chains, asphaltene content and relative diffusivities. In both MWA and ML cases the best predictive models were determined. For such complex mixtures as crude oils are, exceptionally good correlations were obtained, proving that this new and robust model can accurately predict crude oil stability and other important parameters relevant for petroleum industry thus showing a great potential for practical applications.