Background and Objectives: The aim of the present study was to investigate the effect of probiotic supplementation and High Intensity Interval Training (HIIT) on autonomic nervous system using the heart rate variability (HRV), body mass index (BMI), muscle mass index (LMI), fat mass index (FMI) and the relationship between HRV and the aforementioned indices after eight weeks of HIIT training and probiotic supplementation in sedentary women. Materials & Methods: 30 women with a mean age of 32 ± 8 years were randomly divided into three groups of ten: HIIT, probiotics, and HIIT + probiotics. The training groups performed three sessions per week for eight weeks. Each session included two sets of 5 HIIT based on running and two sets of 5 HIIT based on handball. Probiotic supplementation was consumed on training days in the form of a capsule containing 109 CFU of the bacterial mixture. Results: The decrease in FMI and BMI after eight weeks of intervention was not significant in any of the groups, but the difference in FMI between the probiotic+HIIT and probiotic groups was significant. The increase in LMI was not significant in any of the groups, and no significant difference was observed between the three groups. All three interventions significantly improved Ln SDNN, Ln RMSSD. The probiotic and HIIT+probiotic significantly increased PNN50. Probiotic significantly reduced Ln LF/Ln HF (P≤0.05), but no significant difference was observed between the three groups. In the present study a significant relationship was observed between Ln RMSSD and FMI (P≤0.05). Conclusion: The combination of HIIT and probiotic supplementation is likely to be more beneficial in improving body composition than either alone, and both HIIT and probiotic supplementation can help modulate the autonomic nervous system.