Symptoms such as ventricular arrhythmias in Brugada syndrome (BS) typically occur at rest, especially during sleep, suggesting that the autonomic nervous system (ANS) function may be relevant in the arrhythmogenesis of the disease. The aim of this work was to assess the ANS response captured by nonlinear heart rate variability (HRV) measures in 69 patients diagnosed with BS, who underwent a standardized physical stress test. Heart rate complexity (HRC) was evaluated by the power-law scaling analysis (beta slope) during rest, exercise, recovery and rest post-recovery, in order to discriminate between symptomatic and asymptomatic BS patients. Symptomatic patients showed a significant reduction in HRC in comparison to asymptomatic subjects, after exertion (p = 0.015); during the whole recovery period (p = 0.023), and in particular within the passive recovery phase (p = 0.025), as well as during rest post-recovery (p = 0.022). Based on these results, symptoms could be associated with a lower ANS complexity during the stress test stages where parasympathetic activity is predominant. Therefore, the proposed HRV indicators could be of help in the risk stratification of asymptomatic patients.