Background and aim: Results from randomized controlled trials indicate that no single diet performs better than other for all people living with obesity. Regardless of the diet plan, there is always large inter-individual variability in weight changes, with some individuals losing weight and some not losing or even gaining weight. This raises the possibility that, for different individuals, the optimal diet for successful weight loss may differ. The current study utilized machine learning to build a predictive model for successful weight loss in subjects with overweight or obesity on a New Nordic Diet (NND). Methods: Ninety-one subjects consumed an NND ad libitum for 26 weeks. Based on their weight loss, individuals were classified as responders (weight loss ≥5%, n = 46) or non-responders (weight loss <2%, n = 24). We used clinical baseline data combined with baseline urine and plasma untargeted metabolomics data from two different analytical platforms, resulting in a data set including 2,766 features, and employed symbolic regression (QLattice) to develop a predictive model for weight loss success. Results: There were no differences in clinical parameters at baseline between responders and non-responders, except age (47 ± 13 vs. 39 ± 11 years, respectively, p = 0.009). The final predictive model for weight loss contained adipic acid and argininic acid from urine (both metabolites were found at lower levels in responders) and generalized from the training (AUC 0.88) to the test set (AUC 0.81). Responders were also able to maintain a weight loss of 4.3% in a 12 month follow-up period. Conclusion: We identified a model containing two metabolites that were able to predict the likelihood of achieving a clinically significant weight loss on an ad libitum NND. This work demonstrates that models based on an untargeted multi-platform metabolomics approach can be used to optimize precision dietary treatment for obesity.