Transcutaneous auricular vagus nerve stimulation (taVNS) is an emerging treatment method for psychiatric and cardiovascular diseases, and its stimulation intensity setting needs to adjust the stimulation current to the pain threshold and then reduce its amplitude. This approach not only lacks uniformity, but it also has an impact on treatment efficacy and comfort. To estimate taVNS pain thresholds, this research provides a novel technique that combines HRV characteristics and machine learning regression models. Based on the experimentally collected data, the prediction accuracy of HRV characteristics as input to various machine learning models was systematically compared. The results show that the combination of HRV characteristics and extra trees regression has the best performance, and the use of genetic algorithm to remove redundant features can effectively improve the model prediction performance. The root-mean-square error ranges from 1.18 to 1.56, while the mean-square error ranges from 0.77 to 0.96. This method can be utilized to predict taVNS stimulation intensity and has a positive effect on the treatment effect of subjects during taVNS.