A critical component of the treatment for anxiety disorders is the extinction of fear via repeated exposure to the feared stimulus. This process is strongly dependent on successful memory formation and consolidation. Stimulation of the vagus nerve enhances memory formation in both animals and humans. The objective of this study was to assess whether transcutaneous stimulation of the vagus nerve (tVNS) can accelerate extinction memory formation and retention in fear conditioned humans. To assess fear conditioning and subsequent fear extinction, we assessed US expectancy ratings, fear potentiated startle responses and phasic heart rate responses. We conducted a randomized controlled trial in thirty-one healthy participants. After fear conditioning participants were randomly assigned to receive tVNS or sham stimulation during the extinction phase. Retention of extinction memory was tested 24h later. tVNS accelerated explicit fear extinction learning (US expectancy ratings), but did not lead to better retention of extinction memory 24h later. We did not find a differential physiological conditioning response during the acquisition of fear and thus were unable to assess potential effects of tVNS on the extinction of physiological indices of fear. These findings complement recent studies that suggest vagus nerve stimulation could be a promising tool to improve memory consolidation and fear extinction.