Sexual satisfaction has been robustly associated with relationship and individual well-being. Previous studies have found several individual (e.g., gender, self-esteem, and attachment) and relational (e.g., relationship satisfaction, relationship length, and sexual desire) factors that predict sexual satisfaction. The aim of the present study was to identify which variables are the strongest, and the least strong, predictors of sexual satisfaction using modern machine learning. Previous research has relied primarily on traditional statistical models which are limited in their ability to estimate a large number of predictors, non-linear associations, and complex interactions. Through a machine learning algorithm, random forest (a potentially more flexible extension of decision trees), we predicted sexual satisfaction across two samples (total N = 1846; includes 754 individuals forming 377 couples). We also used a game theoretic interpretation technique, Shapley values, which allowed us to estimate the size and direction of the effect of each predictor variable on the model outcome. Findings showed that sexual satisfaction is highly predictable (48–62% of variance explained) with relationship variables (relationship satisfaction, importance of sex in relationship, romantic love, and dyadic desire) explaining the most variance in sexual satisfaction. The study highlighted important factors to focus on in future research and interventions.