Previous research suggested increased cardiac interoceptive accuracy after 24-h food-deprivation by means of the heartbeat tracking task. The present study investigated if 16-h of voluntary fasting shows similar effects and whether changes in interoceptive accuracy are accompanied by changes in autonomic function. In two independent within-subjects studies two measures of interoceptive accuracy, the heartbeat tracking task and the heartbeat discrimination task were applied. In study 1 (n = 24) and study 2 (n = 72) vagally-mediated HRV increases and heart rate decreases were observed. Stronger effects of fasting on vagally-mediated HRV went along with a higher interoceptive accuracy increase in the heartbeat tracking task. Furthermore, the fasting associated changes in interoceptive accuracy in both tasks were significantly associated, suggesting that these tasks are suitable to track changes in cardiac interoception. Taken together, fasting of 16-h might be suitable to increase participants\' parasympathetic efference, thereby facilitating interoception.