Auditioning is at the very center of educational and professional life in music and is associated with significant psychophysical demands. Knowledge of how these demands affect cardiovascular responses to psychosocial pressure is essential for developing strategies to both manage stress and understand optimal performance states. To this end, we recorded the electrocardiograms (ECGs) of 16 musicians (11 violinists and 5 flutists) before and during performances in both low- and high-stress conditions: with no audience and in front of an audition panel, respectively. The analysis consisted of the detection of R-peaks in the ECGs to extract heart rate variability (HRV) from the notoriously noisy real-world ECGs. Our data analysis approach spanned both standard (temporal and spectral) and advanced (structural complexity) techniques. The complexity science approaches—namely, multiscale sample entropy and multiscale fuzzy entropy—indicated a statistically significant decrease in structural complexity in HRV from the low- to the high-stress condition and an increase in structural complexity from the pre-performance to performance period, thus confirming the complexity loss theory and a loss in degrees of freedom due to stress. Results from the spectral analyses also suggest that the stress responses in the female participants were more parasympathetically driven than those of the male participants. In conclusion, our findings suggest that interventions to manage stress are best targeted at the sensitive pre-performance period, before an audition begins.