Nowadays, psychological stress represents a burdensome condition affecting an increasing number of subjects, in turn putting into practice several strategies to cope with this issue, including the administration of relaxation protocols, often performed in non-structured environments, like workplaces, and constrained within short times. Here, we performed a quick relaxation protocol based on a short audio and video, and analyzed physiological signals related to the autonomic nervous system (ANS) activity, including electrocardiogram (ECG) and galvanic skin response (GSR). Based on the features extracted, machine learning was applied to discriminate between subjects benefitting from the protocol and those with negative or no effects. Twenty-four healthy volunteers were enrolled for the protocol, equally and randomly divided into Group A, performing an audio-video + video-only relaxation, and Group B, performing an audio-video + audio-only protocol. From the ANS point of view, Group A subjects displayed a significant difference in the heart rate variability-related parameter SDNN across the test phases, whereas both groups displayed a different GSR response, albeit at different levels, with Group A displaying greater differences across phases with respect to Group B. Overall, the majority of the volunteers enrolled self-reported an improvement of their well-being status, according to structured questionnaires. The use of neural networks helped in discriminating those with a positive effect of the relaxation protocol from those with a negative/neutral impact based on basal autonomic features with a 79.2% accuracy. The results obtained demonstrated a significant heterogeneity in autonomic effects of the relaxation, highlighting the importance of maintaining a structured, well-defined protocol to produce significant benefits at the ANS level. Machine learning approaches can be useful to predict the outcome of such protocols, therefore providing subjects less prone to positive responses with personalized advice that could improve the effect of such protocols on self-relaxation perception.